Subject: [PATCH v6 0/6] Xdiff cleanup part 3

From: "Ezekiel Newren via GitGitGadget" <[email-masked]>
Date: Wed, 29 Apr 2026 22:08:09 +0000

Changes in v6:

 * implement suggestions by Phillip Wood [1,2]

Phillip's second "if" in [1] differs from his first one. In my changes I
made both of them structurally the same.

Something I'm confused by is the range-diff of patch 5. I'm confused why
range-diff states that this is different at all. I don't think this is a
problem, I just don't like not being able to explain a difference pointed
out by range-diff.

5: 88c68fa89a ! 5: 099b08c33f xdiff/xdl_cleanup_records: make setting action
easier to follow @@ xdiff/xprepare.c: static int
xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t * + action1[i] =
INVESTIGATE; }

-   for (i = xdf2->dstart; i <= xdf2->dend; i++) {
+   if (need_min) {
+@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
            size_t mph2 = xdf2->recs[i].minimal_perfect_hash;
            rcrec = cf->rcrecs[mph2];
            nm = rcrec ? rcrec->len1 : 0;

[1] limits
https://lore.kernel.org/git/[email-masked]/
[2] action execution
https://lore.kernel.org/git/[email-masked]/

Changes in v5:

 * drop commit "xdiff/xdl_cleanup_records: simplify INVESTIGATE handling for
   clarity".
 * add braces around the else clause

I didn't see a better way to rewrite how action is used so I reverted to
what it used to be.

Changes in v4:

 * Change SIZE_MAX to PTRDIFF_MAX.

Changes in v3:

 * run make DEVELOPER=1 on each commit and fix all compiler issues

v2 is a radical departure from v1 Changes in v2:

 * make the flow of xdl_cleanup_records() easier to follow

There is no performance or behavioral change introduced in this patch
series.

=== original cover letter bellow ===

Patch series summary:

 * patch 1: Introduce the ivec type
 * patch 2: Create the function xdl_do_classic_diff()
 * patches 3-4: generic cleanup
 * patches 5-8: convert from dstart/dend (in xdfile_t) to
   delta_start/delta_end (in xdfenv_t)
 * patches 9-10: move xdl_cleanup_records(), and related, from xprepare.c to
   xdiffi.c

Things that will be addressed in future patch series:

 * Make xdl_cleanup_records() easier to read
 * convert recs/nrec into an ivec
 * convert changed to an ivec
 * remove reference_index/nreff from xdfile_t and turn it into an ivec
 * splitting minimal_perfect_hash out as its own ivec
 * improve the performance of the classifier and parsing/hashing lines

=== before this patch series typedef struct s_xdfile { xrecord_t *recs;
size_t nrec; ptrdiff_t dstart, dend; bool *changed; size_t *reference_index;
size_t nreff; } xdfile_t;

typedef struct s_xdfenv { xdfile_t xdf1, xdf2; } xdfenv_t;

=== after this patch series typedef struct s_xdfile { xrecord_t *recs;
size_t nrec; bool *changed; size_t *reference_index; size_t nreff; }
xdfile_t;

typedef struct s_xdfenv { xdfile_t xdf1, xdf2; size_t delta_start,
delta_end; size_t mph_size; } xdfenv_t;

Ezekiel Newren (6):
  xdiff/xdl_cleanup_records: delete local recs pointer
  xdiff: use unambiguous types in xdl_bogo_sqrt()
  xdiff/xdl_cleanup_records: use unambiguous types
  xdiff/xdl_cleanup_records: make limits more clear
  xdiff/xdl_cleanup_records: make setting action easier to follow
  xdiff/xdl_cleanup_records: make execution of action easier to follow

 xdiff/xdiffi.c   |  2 +-
 xdiff/xprepare.c | 97 ++++++++++++++++++++++++++++++++++--------------
 xdiff/xutils.c   |  4 +-
 xdiff/xutils.h   |  2 +-
 4 files changed, 73 insertions(+), 32 deletions(-)

base-commit: ca1db8a0f7dc0dbea892e99f5b37c5fe5861be71
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2156%2Fezekielnewren%2Fxdiff-cleanup-3-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2156/ezekielnewren/xdiff-cleanup-3-v6
Pull-Request: https://github.com/git/git/pull/2156

Range-diff vs v5:

 1:  b31924a949 = 1:  b31924a949 xdiff/xdl_cleanup_records: delete local recs pointer
 2:  1822166fef = 2:  1822166fef xdiff: use unambiguous types in xdl_bogo_sqrt()
 3:  85aa0da90c = 3:  85aa0da90c xdiff/xdl_cleanup_records: use unambiguous types
 4:  fec2b0f38a ! 4:  51c62ed454 xdiff/xdl_cleanup_records: make limits more clear
     @@ Commit message
            * The additional condition `!need_min` is redudant now, remove it.
          Best viewed with --color-words.
      
     +    Helped-by: Phillip Wood
          Signed-off-by: Ezekiel Newren <[email-masked]>
      
       ## xdiff/xprepare.c ##
     @@ xdiff/xprepare.c: static bool xdl_clean_mmatch(uint8_t const *action, ptrdiff_t
       	uint8_t *action1 = NULL, *action2 = NULL;
       	bool need_min = !!(cf->flags & XDF_NEED_MINIMAL);
      @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
     - 		goto cleanup;
     - 	}
     - 
     -+	if (need_min) {
     -+		/* i.e. infinity */
     -+		mlim1 = PTRDIFF_MAX;
     -+		mlim2 = PTRDIFF_MAX;
     -+	} else {
     -+		mlim1 = XDL_MIN(xdl_bogosqrt(xdf1->nrec), XDL_MAX_EQLIMIT);
     -+		mlim2 = XDL_MIN(xdl_bogosqrt(xdf2->nrec), XDL_MAX_EQLIMIT);
     -+	}
     -+
       	/*
       	 * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
       	 */
      -	if ((mlim = (long)xdl_bogosqrt((uint64_t)xdf1->nrec)) > XDL_MAX_EQLIMIT)
      -		mlim = XDL_MAX_EQLIMIT;
     ++	if (need_min) {
     ++		/* i.e. infinity */
     ++		mlim1 = PTRDIFF_MAX;
     ++	} else {
     ++		mlim1 = xdl_bogosqrt((uint64_t)xdf1->nrec);
     ++		if (mlim1 > XDL_MAX_EQLIMIT)
     ++			mlim1 = XDL_MAX_EQLIMIT;
     ++	}
       	for (i = xdf1->dstart; i <= xdf1->dend; i++) {
       		size_t mph1 = xdf1->recs[i].minimal_perfect_hash;
       		rcrec = cf->rcrecs[mph1];
     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
       
      -	if ((mlim = (long)xdl_bogosqrt((uint64_t)xdf2->nrec)) > XDL_MAX_EQLIMIT)
      -		mlim = XDL_MAX_EQLIMIT;
     ++	if (need_min) {
     ++		/* i.e. infinity */
     ++		mlim2 = PTRDIFF_MAX;
     ++	} else {
     ++		mlim2 = xdl_bogosqrt((uint64_t)xdf2->nrec);
     ++		if (mlim2 > XDL_MAX_EQLIMIT)
     ++			mlim2 = XDL_MAX_EQLIMIT;
     ++	}
       	for (i = xdf2->dstart; i <= xdf2->dend; i++) {
       		size_t mph2 = xdf2->recs[i].minimal_perfect_hash;
       		rcrec = cf->rcrecs[mph2];
 5:  88c68fa89a ! 5:  45ad2ae62d xdiff/xdl_cleanup_records: make setting action easier to follow
     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
      +			action1[i] = INVESTIGATE;
       	}
       
     - 	for (i = xdf2->dstart; i <= xdf2->dend; i++) {
     + 	if (need_min) {
     +@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
       		size_t mph2 = xdf2->recs[i].minimal_perfect_hash;
       		rcrec = cf->rcrecs[mph2];
       		nm = rcrec ? rcrec->len1 : 0;
 6:  699e198fa9 ! 6:  a5174802f4 xdiff/xdl_cleanup_records: put braces around the else clause
     @@ Metadata
      Author: Ezekiel Newren <[email-masked]>
      
       ## Commit message ##
     -    xdiff/xdl_cleanup_records: put braces around the else clause
     +    xdiff/xdl_cleanup_records: make execution of action easier to follow
      
     +    Helped-by: Phillip Wood
          Signed-off-by: Ezekiel Newren <[email-masked]>
      
       ## xdiff/xprepare.c ##
      @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
     - 		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) {
     + 	 */
     + 	xdf1->nreff = 0;
     + 	for (i = xdf1->dstart; i <= xdf1->dend; i++) {
     +-		if (action1[i] == KEEP ||
     +-		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) {
     ++		uint8_t action = action1[i];
     ++
     ++		if (action == INVESTIGATE) {
     ++			if (!xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))
     ++				action = KEEP;
     ++			else
     ++				action = DISCARD;
     ++		}
     ++
     ++		if (action == KEEP) {
       			xdf1->reference_index[xdf1->nreff++] = i;
     - 			/* changed[i] remains false, i.e. keep */
     +-			/* changed[i] remains false, i.e. keep */
      -		} else
     -+		} else {
     ++			/* changed[i] remains false */
     ++		} else if (action == DISCARD) {
       			xdf1->changed[i] = true;
     - 			/* i.e. discard */
     +-			/* i.e. discard */
     ++		} else {
     ++			BUG("Illegal state for action");
      +		}
       	}
       
       	xdf2->nreff = 0;
     -@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
     - 		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) {
     + 	for (i = xdf2->dstart; i <= xdf2->dend; i++) {
     +-		if (action2[i] == KEEP ||
     +-		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) {
     ++		uint8_t action = action2[i];
     ++
     ++		if (action == INVESTIGATE) {
     ++			if (!xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))
     ++				action = KEEP;
     ++			else
     ++				action = DISCARD;
     ++		}
     ++
     ++		if (action == KEEP) {
       			xdf2->reference_index[xdf2->nreff++] = i;
     - 			/* changed[i] remains false, i.e. keep */
     +-			/* changed[i] remains false, i.e. keep */
      -		} else
     -+		} else {
     ++			/* changed[i] remains false */
     ++		} else if (action == DISCARD) {
       			xdf2->changed[i] = true;
     - 			/* i.e. discard */
     +-			/* i.e. discard */
     ++		} else {
     ++			BUG("Illegal state for action");
      +		}
       	}

-- 
gitgitgadget