To: vim_dev@googlegroups.com
Subject: Patch 9.0.1418
Fcc: outbox
From: Bram Moolenaar <Bram@moolenaar.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
------------

Patch 9.0.1418
Problem:    The included xdiff code is a bit outdated.
Solution:   Sync with the latest git xdiff code. (Yee Cheng Chin,
            closes #12181)
Files:      src/xdiff/README.txt, src/xdiff/xdiff.h, src/xdiff/xdiffi.c,
            src/xdiff/xdiffi.h, src/xdiff/xemit.c, src/xdiff/xhistogram.c,
            src/xdiff/xmacros.h, src/xdiff/xpatience.c, src/xdiff/xprepare.c,
            src/xdiff/xutils.c, src/xdiff/xutils.h


*** ../vim-9.0.1417/src/xdiff/README.txt	2021-09-01 10:08:10.000000000 +0100
--- src/xdiff/README.txt	2023-03-20 17:20:10.111087422 +0000
***************
*** 1,6 ****
  The files in this directory come from the xdiff implementation in git.
  You can find it here: https://github.com/git/git/tree/master/xdiff
! The files were last updated August 31, 2021 from git release v.2.33.0
  
  This is originally based on libxdiff, which can be found here:
  http://www.xmailserver.org/xdiff-lib.html
--- 1,6 ----
  The files in this directory come from the xdiff implementation in git.
  You can find it here: https://github.com/git/git/tree/master/xdiff
! The files were last updated March 17, 2023 from git release v.2.40.0
  
  This is originally based on libxdiff, which can be found here:
  http://www.xmailserver.org/xdiff-lib.html
*** ../vim-9.0.1417/src/xdiff/xdiff.h	2021-08-31 19:27:29.000000000 +0100
--- src/xdiff/xdiff.h	2023-03-20 17:20:10.111087422 +0000
***************
*** 66,71 ****
--- 66,72 ----
  
  /* merge output styles */
  #define XDL_MERGE_DIFF3 1
+ #define XDL_MERGE_ZEALOUS_DIFF3 2
  
  typedef struct s_mmfile {
  	char *ptr;
***************
*** 126,131 ****
--- 127,133 ----
  #endif
  
  #define xdl_malloc(x) lalloc((x), TRUE)
+ #define xdl_calloc(n, sz) lalloc_clear(n*sz, TRUE)
  #define xdl_free(ptr) vim_free(ptr)
  #define xdl_realloc(ptr,x) vim_realloc((ptr),(x))
  
*** ../vim-9.0.1417/src/xdiff/xdiffi.c	2021-08-31 19:27:29.000000000 +0100
--- src/xdiff/xdiffi.c	2023-03-20 17:20:10.111087422 +0000
***************
*** 315,330 ****
  	long *kvd, *kvdf, *kvdb;
  	xdalgoenv_t xenv;
  	diffdata_t dd1, dd2;
  
! 	if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF)
! 		return xdl_do_patience_diff(mf1, mf2, xpp, xe);
! 
! 	if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)
! 		return xdl_do_histogram_diff(mf1, mf2, xpp, xe);
  
! 	if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {
  
! 		return -1;
  	}
  
  	/*
--- 315,333 ----
  	long *kvd, *kvdf, *kvdb;
  	xdalgoenv_t xenv;
  	diffdata_t dd1, dd2;
+ 	int res;
  
! 	if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0)
! 		return -1;
  
! 	if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF) {
! 		res = xdl_do_patience_diff(xpp, xe);
! 		goto out;
! 	}
  
! 	if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) {
! 		res = xdl_do_histogram_diff(xpp, xe);
! 		goto out;
  	}
  
  	/*
***************
*** 334,340 ****
  	 * One is to store the forward path and one to store the backward path.
  	 */
  	ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
! 	if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) {
  
  		xdl_free_env(xe);
  		return -1;
--- 337,343 ----
  	 * One is to store the forward path and one to store the backward path.
  	 */
  	ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
! 	if (!XDL_ALLOC_ARRAY(kvd, 2 * ndiags + 2)) {
  
  		xdl_free_env(xe);
  		return -1;
***************
*** 359,375 ****
  	dd2.rchg = xe->xdf2.rchg;
  	dd2.rindex = xe->xdf2.rindex;
  
! 	if (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,
! 			 kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, &xenv) < 0) {
! 
! 		xdl_free(kvd);
! 		xdl_free_env(xe);
! 		return -1;
! 	}
! 
  	xdl_free(kvd);
  
! 	return 0;
  }
  
  
--- 362,376 ----
  	dd2.rchg = xe->xdf2.rchg;
  	dd2.rindex = xe->xdf2.rindex;
  
! 	res = xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,
! 			   kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0,
! 			   &xenv);
  	xdl_free(kvd);
+  out:
+ 	if (res < 0)
+ 		xdl_free_env(xe);
  
! 	return res;
  }
  
  
***************
*** 390,401 ****
  }
  
  
! static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags)
  {
! 	return (rec1->ha == rec2->ha &&
! 		xdl_recmatch(rec1->ptr, rec1->size,
! 			     rec2->ptr, rec2->size,
! 			     flags));
  }
  
  /*
--- 391,399 ----
  }
  
  
! static int recs_match(xrecord_t *rec1, xrecord_t *rec2)
  {
! 	return (rec1->ha == rec2->ha);
  }
  
  /*
***************
*** 759,768 ****
   * following group, expand this group to include it. Return 0 on success or -1
   * if g cannot be slid down.
   */
! static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g, long flags)
  {
  	if (g->end < xdf->nrec &&
! 	    recs_match(xdf->recs[g->start], xdf->recs[g->end], flags)) {
  		xdf->rchg[g->start++] = 0;
  		xdf->rchg[g->end++] = 1;
  
--- 757,766 ----
   * following group, expand this group to include it. Return 0 on success or -1
   * if g cannot be slid down.
   */
! static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g)
  {
  	if (g->end < xdf->nrec &&
! 	    recs_match(xdf->recs[g->start], xdf->recs[g->end])) {
  		xdf->rchg[g->start++] = 0;
  		xdf->rchg[g->end++] = 1;
  
***************
*** 780,789 ****
   * into a previous group, expand this group to include it. Return 0 on success
   * or -1 if g cannot be slid up.
   */
! static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g, long flags)
  {
  	if (g->start > 0 &&
! 	    recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1], flags)) {
  		xdf->rchg[--g->start] = 1;
  		xdf->rchg[--g->end] = 0;
  
--- 778,787 ----
   * into a previous group, expand this group to include it. Return 0 on success
   * or -1 if g cannot be slid up.
   */
! static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g)
  {
  	if (g->start > 0 &&
! 	    recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1])) {
  		xdf->rchg[--g->start] = 1;
  		xdf->rchg[--g->end] = 0;
  
***************
*** 839,845 ****
  			end_matching_other = -1;
  
  			/* Shift the group backward as much as possible: */
! 			while (!group_slide_up(xdf, &g, flags))
  				if (group_previous(xdfo, &go))
  					xdl_bug("group sync broken sliding up");
  
--- 837,843 ----
  			end_matching_other = -1;
  
  			/* Shift the group backward as much as possible: */
! 			while (!group_slide_up(xdf, &g))
  				if (group_previous(xdfo, &go))
  					xdl_bug("group sync broken sliding up");
  
***************
*** 854,860 ****
  
  			/* Now shift the group forward as far as possible: */
  			while (1) {
! 				if (group_slide_down(xdf, &g, flags))
  					break;
  				if (group_next(xdfo, &go))
  					xdl_bug("group sync broken sliding down");
--- 852,858 ----
  
  			/* Now shift the group forward as far as possible: */
  			while (1) {
! 				if (group_slide_down(xdf, &g))
  					break;
  				if (group_next(xdfo, &go))
  					xdl_bug("group sync broken sliding down");
***************
*** 881,887 ****
  			 * other file that it can align with.
  			 */
  			while (go.end == go.start) {
! 				if (group_slide_up(xdf, &g, flags))
  					xdl_bug("match disappeared");
  				if (group_previous(xdfo, &go))
  					xdl_bug("group sync broken sliding to match");
--- 879,885 ----
  			 * other file that it can align with.
  			 */
  			while (go.end == go.start) {
! 				if (group_slide_up(xdf, &g))
  					xdl_bug("match disappeared");
  				if (group_previous(xdfo, &go))
  					xdl_bug("group sync broken sliding to match");
***************
*** 924,930 ****
  			}
  
  			while (g.end > best_shift) {
! 				if (group_slide_up(xdf, &g, flags))
  					xdl_bug("best shift unreached");
  				if (group_previous(xdfo, &go))
  					xdl_bug("group sync broken sliding to blank line");
--- 922,928 ----
  			}
  
  			while (g.end > best_shift) {
! 				if (group_slide_up(xdf, &g))
  					xdl_bug("best shift unreached");
  				if (group_previous(xdfo, &go))
  					xdl_bug("group sync broken sliding to blank line");
*** ../vim-9.0.1417/src/xdiff/xdiffi.h	2021-08-31 19:27:29.000000000 +0100
--- src/xdiff/xdiffi.h	2023-03-20 17:20:10.111087422 +0000
***************
*** 56,64 ****
  void xdl_free_script(xdchange_t *xscr);
  int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
  		  xdemitconf_t const *xecfg);
! int xdl_do_patience_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
! 		xdfenv_t *env);
! int xdl_do_histogram_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
! 		xdfenv_t *env);
  
  #endif /* #if !defined(XDIFFI_H) */
--- 56,62 ----
  void xdl_free_script(xdchange_t *xscr);
  int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
  		  xdemitconf_t const *xecfg);
! int xdl_do_patience_diff(xpparam_t const *xpp, xdfenv_t *env);
! int xdl_do_histogram_diff(xpparam_t const *xpp, xdfenv_t *env);
  
  #endif /* #if !defined(XDIFFI_H) */
*** ../vim-9.0.1417/src/xdiff/xemit.c	2021-09-13 21:14:59.000000000 +0100
--- src/xdiff/xemit.c	2023-03-20 17:20:10.111087422 +0000
***************
*** 65,71 ****
  			*xscr = xch;
  	}
  
! 	if (*xscr == NULL)
  		return NULL;
  
  	lxch = *xscr;
--- 65,71 ----
  			*xscr = xch;
  	}
  
! 	if (!*xscr)
  		return NULL;
  
  	lxch = *xscr;
***************
*** 96,102 ****
  
  
  #if 0
! static long def_ff(const char *rec, long len, char *buf, long sz, void *priv UNUSED)
  {
  	if (len > 0 &&
  			(isalpha((unsigned char)*rec) || /* identifier? */
--- 96,102 ----
  
  
  #if 0
! static long def_ff(const char *rec, long len, char *buf, long sz)
  {
  	if (len > 0 &&
  			(isalpha((unsigned char)*rec) || /* identifier? */
***************
*** 120,126 ****
  	const char *rec;
  	long len = xdl_get_rec(xdf, ri, &rec);
  	if (!xecfg->find_func)
! 		return def_ff(rec, len, buf, sz, xecfg->find_func_priv);
  	return xecfg->find_func(rec, len, buf, sz, xecfg->find_func_priv);
  }
  #endif
--- 120,126 ----
  	const char *rec;
  	long len = xdl_get_rec(xdf, ri, &rec);
  	if (!xecfg->find_func)
! 		return def_ff(rec, len, buf, sz);
  	return xecfg->find_func(rec, len, buf, sz, xecfg->find_func_priv);
  }
  #endif
*** ../vim-9.0.1417/src/xdiff/xhistogram.c	2021-08-31 19:27:29.000000000 +0100
--- src/xdiff/xhistogram.c	2023-03-20 17:20:10.111087422 +0000
***************
*** 88,106 ****
  #define REC(env, s, l) \
  	(env->xdf##s.recs[l - 1])
  
! static int cmp_recs(xpparam_t const *xpp,
! 	xrecord_t *r1, xrecord_t *r2)
  {
! 	return r1->ha == r2->ha &&
! 		xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,
! 			    xpp->flags);
! }
  
! #define CMP_ENV(xpp, env, s1, l1, s2, l2) \
! 	(cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2)))
  
  #define CMP(i, s1, l1, s2, l2) \
! 	(cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2)))
  
  #define TABLE_HASH(index, side, line) \
  	XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)
--- 88,101 ----
  #define REC(env, s, l) \
  	(env->xdf##s.recs[l - 1])
  
! static int cmp_recs(xrecord_t *r1, xrecord_t *r2)
  {
! 	return r1->ha == r2->ha;
  
! }
  
  #define CMP(i, s1, l1, s2, l2) \
! 	(cmp_recs(REC(i->env, s1, l1), REC(i->env, s2, l2)))
  
  #define TABLE_HASH(index, side, line) \
  	XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)
***************
*** 256,262 ****
  		    int line1, int count1, int line2, int count2)
  {
  	int b_ptr;
! 	int sz, ret = -1;
  	struct histindex index;
  
  	memset(&index, 0, sizeof(index));
--- 251,257 ----
  		    int line1, int count1, int line2, int count2)
  {
  	int b_ptr;
! 	int ret = -1;
  	struct histindex index;
  
  	memset(&index, 0, sizeof(index));
***************
*** 270,292 ****
  	index.rcha.head = NULL;
  
  	index.table_bits = xdl_hashbits(count1);
! 	sz = index.records_size = 1 << index.table_bits;
! 	sz *= sizeof(struct record *);
! 	if (!(index.records = (struct record **) xdl_malloc(sz)))
  		goto cleanup;
- 	memset(index.records, 0, sz);
  
! 	sz = index.line_map_size = count1;
! 	sz *= sizeof(struct record *);
! 	if (!(index.line_map = (struct record **) xdl_malloc(sz)))
  		goto cleanup;
- 	memset(index.line_map, 0, sz);
  
! 	sz = index.line_map_size;
! 	sz *= sizeof(unsigned int);
! 	if (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz)))
  		goto cleanup;
- 	memset(index.next_ptrs, 0, sz);
  
  	/* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */
  	if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)
--- 265,280 ----
  	index.rcha.head = NULL;
  
  	index.table_bits = xdl_hashbits(count1);
! 	index.records_size = 1 << index.table_bits;
! 	if (!XDL_CALLOC_ARRAY(index.records, index.records_size))
  		goto cleanup;
  
! 	index.line_map_size = count1;
! 	if (!XDL_CALLOC_ARRAY(index.line_map, index.line_map_size))
  		goto cleanup;
  
! 	if (!XDL_CALLOC_ARRAY(index.next_ptrs, index.line_map_size))
  		goto cleanup;
  
  	/* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */
  	if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)
***************
*** 374,385 ****
  	return result;
  }
  
! int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2,
! 	xpparam_t const *xpp, xdfenv_t *env)
  {
- 	if (xdl_prepare_env(file1, file2, xpp, env) < 0)
- 		return -1;
- 
  	return histogram_diff(xpp, env,
  		env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
  		env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
--- 362,369 ----
  	return result;
  }
  
! int xdl_do_histogram_diff(xpparam_t const *xpp, xdfenv_t *env)
  {
  	return histogram_diff(xpp, env,
  		env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
  		env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
*** ../vim-9.0.1417/src/xdiff/xmacros.h	2021-08-31 19:27:29.000000000 +0100
--- src/xdiff/xmacros.h	2023-03-20 17:20:10.111087422 +0000
***************
*** 34,40 ****
  #define XDL_ADDBITS(v,b)	((v) + ((v) >> (b)))
  #define XDL_MASKBITS(b)		((1UL << (b)) - 1)
  #define XDL_HASHLONG(v,b)	(XDL_ADDBITS((unsigned long)(v), b) & XDL_MASKBITS(b))
- #define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0)
  #define XDL_LE32_PUT(p, v) \
  do { \
  	unsigned char *__p = (unsigned char *) (p); \
--- 34,39 ----
***************
*** 50,54 ****
--- 49,71 ----
  		((unsigned long) __p[2]) << 16 | ((unsigned long) __p[3]) << 24; \
  } while (0)
  
+ /* Allocate an array of nr elements, returns NULL on failure */
+ #define XDL_ALLOC_ARRAY(p, nr)				\
+ 	((p) = SIZE_MAX / sizeof(*(p)) >= (size_t)(nr)	\
+ 		? xdl_malloc((nr) * sizeof(*(p)))	\
+ 		: NULL)
+ 
+ /* Allocate an array of nr zeroed out elements, returns NULL on failure */
+ #define XDL_CALLOC_ARRAY(p, nr)	((p) = xdl_calloc(nr, sizeof(*(p))))
+ 
+ /*
+  * Ensure array p can accommodate at least nr elements, growing the
+  * array and updating alloc (which is the number of allocated
+  * elements) as necessary. Frees p and returns -1 on failure, returns
+  * 0 on success
+  */
+ #define XDL_ALLOC_GROW(p, nr, alloc)	\
+ 	(-!((nr) <= (alloc) ||		\
+ 	    ((p) = xdl_alloc_grow_helper((p), (nr), &(alloc), sizeof(*(p))))))
  
  #endif /* #if !defined(XMACROS_H) */
*** ../vim-9.0.1417/src/xdiff/xpatience.c	2021-08-31 19:27:29.000000000 +0100
--- src/xdiff/xpatience.c	2023-03-20 17:20:10.111087422 +0000
***************
*** 69,75 ****
  	} *entries, *first, *last;
  	/* were common records found? */
  	unsigned long has_matches;
- 	mmfile_t *file1, *file2;
  	xdfenv_t *env;
  	xpparam_t const *xpp;
  };
--- 69,74 ----
***************
*** 139,161 ****
   *
   * It is assumed that env has been prepared using xdl_prepare().
   */
! static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,
! 		xpparam_t const *xpp, xdfenv_t *env,
  		struct hashmap *result,
  		int line1, int count1, int line2, int count2)
  {
- 	result->file1 = file1;
- 	result->file2 = file2;
  	result->xpp = xpp;
  	result->env = env;
  
  	/* We know exactly how large we want the hash map */
  	result->alloc = count1 * 2;
! 	result->entries = (struct entry *)
! 		xdl_malloc(result->alloc * sizeof(struct entry));
! 	if (!result->entries)
  		return -1;
- 	memset(result->entries, 0, result->alloc * sizeof(struct entry));
  
  	/* First, fill with entries from the first file */
  	while (count1--)
--- 138,154 ----
   *
   * It is assumed that env has been prepared using xdl_prepare().
   */
! static int fill_hashmap(xpparam_t const *xpp, xdfenv_t *env,
  		struct hashmap *result,
  		int line1, int count1, int line2, int count2)
  {
  	result->xpp = xpp;
  	result->env = env;
  
  	/* We know exactly how large we want the hash map */
  	result->alloc = count1 * 2;
! 	if (!XDL_CALLOC_ARRAY(result->entries, result->alloc))
  		return -1;
  
  	/* First, fill with entries from the first file */
  	while (count1--)
***************
*** 198,206 ****
   * item per sequence length: the sequence with the smallest last
   * element (in terms of line2).
   */
! static struct entry *find_longest_common_sequence(struct hashmap *map)
  {
! 	struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *));
  	int longest = 0, i;
  	struct entry *entry;
  
--- 191,199 ----
   * item per sequence length: the sequence with the smallest last
   * element (in terms of line2).
   */
! static int find_longest_common_sequence(struct hashmap *map, struct entry **res)
  {
! 	struct entry **sequence;
  	int longest = 0, i;
  	struct entry *entry;
  
***************
*** 211,219 ****
  	 */
  	int anchor_i = -1;
  
! 	// Added to silence Coverity.
! 	if (sequence == NULL)
! 		return map->first;
  
  	for (entry = map->first; entry; entry = entry->next) {
  		if (!entry->line2 || entry->line2 == NON_UNIQUE)
--- 204,211 ----
  	 */
  	int anchor_i = -1;
  
! 	if (!XDL_ALLOC_ARRAY(sequence, map->nr))
! 		return -1;
  
  	for (entry = map->first; entry; entry = entry->next) {
  		if (!entry->line2 || entry->line2 == NON_UNIQUE)
***************
*** 234,241 ****
  
  	/* No common unique lines were found */
  	if (!longest) {
  		xdl_free(sequence);
! 		return NULL;
  	}
  
  	/* Iterate starting at the last element, adjusting the "next" members */
--- 226,234 ----
  
  	/* No common unique lines were found */
  	if (!longest) {
+ 		*res = NULL;
  		xdl_free(sequence);
! 		return 0;
  	}
  
  	/* Iterate starting at the last element, adjusting the "next" members */
***************
*** 245,252 ****
  		entry->previous->next = entry;
  		entry = entry->previous;
  	}
  	xdl_free(sequence);
! 	return entry;
  }
  
  static int match(struct hashmap *map, int line1, int line2)
--- 238,246 ----
  		entry->previous->next = entry;
  		entry = entry->previous;
  	}
+ 	*res = entry;
  	xdl_free(sequence);
! 	return 0;
  }
  
  static int match(struct hashmap *map, int line1, int line2)
***************
*** 256,263 ****
  	return record1->ha == record2->ha;
  }
  
! static int patience_diff(mmfile_t *file1, mmfile_t *file2,
! 		xpparam_t const *xpp, xdfenv_t *env,
  		int line1, int count1, int line2, int count2);
  
  static int walk_common_sequence(struct hashmap *map, struct entry *first,
--- 250,256 ----
  	return record1->ha == record2->ha;
  }
  
! static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,
  		int line1, int count1, int line2, int count2);
  
  static int walk_common_sequence(struct hashmap *map, struct entry *first,
***************
*** 288,295 ****
  
  		/* Recurse */
  		if (next1 > line1 || next2 > line2) {
! 			if (patience_diff(map->file1, map->file2,
! 					map->xpp, map->env,
  					line1, next1 - line1,
  					line2, next2 - line2))
  				return -1;
--- 281,287 ----
  
  		/* Recurse */
  		if (next1 > line1 || next2 > line2) {
! 			if (patience_diff(map->xpp, map->env,
  					line1, next1 - line1,
  					line2, next2 - line2))
  				return -1;
***************
*** 328,335 ****
   *
   * This function assumes that env was prepared with xdl_prepare_env().
   */
! static int patience_diff(mmfile_t *file1, mmfile_t *file2,
! 		xpparam_t const *xpp, xdfenv_t *env,
  		int line1, int count1, int line2, int count2)
  {
  	struct hashmap map;
--- 320,326 ----
   *
   * This function assumes that env was prepared with xdl_prepare_env().
   */
! static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,
  		int line1, int count1, int line2, int count2)
  {
  	struct hashmap map;
***************
*** 348,354 ****
  	}
  
  	memset(&map, 0, sizeof(map));
! 	if (fill_hashmap(file1, file2, xpp, env, &map,
  			line1, count1, line2, count2))
  		return -1;
  
--- 339,345 ----
  	}
  
  	memset(&map, 0, sizeof(map));
! 	if (fill_hashmap(xpp, env, &map,
  			line1, count1, line2, count2))
  		return -1;
  
***************
*** 362,386 ****
  		return 0;
  	}
  
! 	first = find_longest_common_sequence(&map);
  	if (first)
  		result = walk_common_sequence(&map, first,
  			line1, count1, line2, count2);
  	else
  		result = fall_back_to_classic_diff(&map,
  			line1, count1, line2, count2);
! 
  	xdl_free(map.entries);
  	return result;
  }
  
! int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2,
! 		xpparam_t const *xpp, xdfenv_t *env)
  {
! 	if (xdl_prepare_env(file1, file2, xpp, env) < 0)
! 		return -1;
! 
! 	/* environment is cleaned up in xdl_diff() */
! 	return patience_diff(file1, file2, xpp, env,
! 			1, env->xdf1.nrec, 1, env->xdf2.nrec);
  }
--- 353,373 ----
  		return 0;
  	}
  
! 	result = find_longest_common_sequence(&map, &first);
! 	if (result)
! 		goto out;
  	if (first)
  		result = walk_common_sequence(&map, first,
  			line1, count1, line2, count2);
  	else
  		result = fall_back_to_classic_diff(&map,
  			line1, count1, line2, count2);
!  out:
  	xdl_free(map.entries);
  	return result;
  }
  
! int xdl_do_patience_diff(xpparam_t const *xpp, xdfenv_t *env)
  {
! 	return patience_diff(xpp, env, 1, env->xdf1.nrec, 1, env->xdf2.nrec);
  }
*** ../vim-9.0.1417/src/xdiff/xprepare.c	2018-09-10 16:39:20.000000000 +0100
--- src/xdiff/xprepare.c	2023-03-20 17:20:10.111087422 +0000
***************
*** 78,92 ****
  
  		return -1;
  	}
! 	if (!(cf->rchash = (xdlclass_t **) xdl_malloc(cf->hsize * sizeof(xdlclass_t *)))) {
  
  		xdl_cha_free(&cf->ncha);
  		return -1;
  	}
- 	memset(cf->rchash, 0, cf->hsize * sizeof(xdlclass_t *));
  
  	cf->alloc = size;
! 	if (!(cf->rcrecs = (xdlclass_t **) xdl_malloc(cf->alloc * sizeof(xdlclass_t *)))) {
  
  		xdl_free(cf->rchash);
  		xdl_cha_free(&cf->ncha);
--- 78,91 ----
  
  		return -1;
  	}
! 	if (!XDL_CALLOC_ARRAY(cf->rchash, cf->hsize)) {
  
  		xdl_cha_free(&cf->ncha);
  		return -1;
  	}
  
  	cf->alloc = size;
! 	if (!XDL_ALLOC_ARRAY(cf->rcrecs, cf->alloc)) {
  
  		xdl_free(cf->rchash);
  		xdl_cha_free(&cf->ncha);
***************
*** 112,118 ****
  	long hi;
  	char const *line;
  	xdlclass_t *rcrec;
- 	xdlclass_t **rcrecs;
  
  	line = rec->ptr;
  	hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
--- 111,116 ----
***************
*** 128,141 ****
  			return -1;
  		}
  		rcrec->idx = cf->count++;
! 		if (cf->count > cf->alloc) {
! 			cf->alloc *= 2;
! 			if (!(rcrecs = (xdlclass_t **) xdl_realloc(cf->rcrecs, cf->alloc * sizeof(xdlclass_t *)))) {
! 
  				return -1;
- 			}
- 			cf->rcrecs = rcrecs;
- 		}
  		cf->rcrecs[rcrec->idx] = rcrec;
  		rcrec->line = line;
  		rcrec->size = rec->size;
--- 126,133 ----
  			return -1;
  		}
  		rcrec->idx = cf->count++;
! 		if (XDL_ALLOC_GROW(cf->rcrecs, cf->count, cf->alloc))
  				return -1;
  		cf->rcrecs[rcrec->idx] = rcrec;
  		rcrec->line = line;
  		rcrec->size = rec->size;
***************
*** 164,170 ****
  	unsigned long hav;
  	char const *blk, *cur, *top, *prev;
  	xrecord_t *crec;
! 	xrecord_t **recs, **rrecs;
  	xrecord_t **rhash;
  	unsigned long *ha;
  	char *rchg;
--- 156,162 ----
  	unsigned long hav;
  	char const *blk, *cur, *top, *prev;
  	xrecord_t *crec;
! 	xrecord_t **recs;
  	xrecord_t **rhash;
  	unsigned long *ha;
  	char *rchg;
***************
*** 178,228 ****
  
  	if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0)
  		goto abort;
! 	if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))
  		goto abort;
  
! 	if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)
! 		hbits = hsize = 0;
! 	else {
! 		hbits = xdl_hashbits((unsigned int) narec);
! 		hsize = 1 << hbits;
! 		if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
! 			goto abort;
! 		memset(rhash, 0, hsize * sizeof(xrecord_t *));
! 	}
  
  	nrec = 0;
! 	if ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {
  		for (top = blk + bsize; cur < top; ) {
  			prev = cur;
  			hav = xdl_hash_record(&cur, top, xpp->flags);
! 			if (nrec >= narec) {
! 				narec *= 2;
! 				if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *))))
! 					goto abort;
! 				recs = rrecs;
! 			}
  			if (!(crec = xdl_cha_alloc(&xdf->rcha)))
  				goto abort;
  			crec->ptr = prev;
  			crec->size = (long) (cur - prev);
  			crec->ha = hav;
  			recs[nrec++] = crec;
! 
! 			if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
! 			    xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
  				goto abort;
  		}
  	}
  
! 	if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char))))
  		goto abort;
- 	memset(rchg, 0, (nrec + 2) * sizeof(char));
  
! 	if (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long))))
! 		goto abort;
! 	if (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long))))
! 		goto abort;
  
  	xdf->nrec = nrec;
  	xdf->recs = recs;
--- 170,211 ----
  
  	if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0)
  		goto abort;
! 	if (!XDL_ALLOC_ARRAY(recs, narec))
  		goto abort;
  
! 	hbits = xdl_hashbits((unsigned int) narec);
! 	hsize = 1 << hbits;
! 	if (!XDL_CALLOC_ARRAY(rhash, hsize))
! 		goto abort;
  
  	nrec = 0;
! 	if ((cur = blk = xdl_mmfile_first(mf, &bsize))) {
  		for (top = blk + bsize; cur < top; ) {
  			prev = cur;
  			hav = xdl_hash_record(&cur, top, xpp->flags);
! 			if (XDL_ALLOC_GROW(recs, nrec + 1, narec))
! 				goto abort;
  			if (!(crec = xdl_cha_alloc(&xdf->rcha)))
  				goto abort;
  			crec->ptr = prev;
  			crec->size = (long) (cur - prev);
  			crec->ha = hav;
  			recs[nrec++] = crec;
! 			if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
  				goto abort;
  		}
  	}
  
! 	if (!XDL_CALLOC_ARRAY(rchg, nrec + 2))
  		goto abort;
  
! 	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
! 	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {
! 		if (!XDL_ALLOC_ARRAY(rindex, nrec + 1))
! 			goto abort;
! 		if (!XDL_ALLOC_ARRAY(ha, nrec + 1))
! 			goto abort;
! 	}
  
  	xdf->nrec = nrec;
  	xdf->recs = recs;
***************
*** 279,286 ****
  	enl1 = xdl_guess_lines(mf1, sample) + 1;
  	enl2 = xdl_guess_lines(mf2, sample) + 1;
  
! 	if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF &&
! 	    xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
  		return -1;
  
  	if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
--- 262,268 ----
  	enl1 = xdl_guess_lines(mf1, sample) + 1;
  	enl2 = xdl_guess_lines(mf2, sample) + 1;
  
! 	if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
  		return -1;
  
  	if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
***************
*** 305,312 ****
  		return -1;
  	}
  
! 	if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)
! 		xdl_free_classifier(&cf);
  
  	return 0;
  }
--- 287,293 ----
  		return -1;
  	}
  
! 	xdl_free_classifier(&cf);
  
  	return 0;
  }
***************
*** 388,398 ****
  	xdlclass_t *rcrec;
  	char *dis, *dis1, *dis2;
  
! 	if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {
! 
  		return -1;
- 	}
- 	memset(dis, 0, xdf1->nrec + xdf2->nrec + 2);
  	dis1 = dis;
  	dis2 = dis1 + xdf1->nrec + 1;
  
--- 369,376 ----
  	xdlclass_t *rcrec;
  	char *dis, *dis1, *dis2;
  
! 	if (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))
  		return -1;
  	dis1 = dis;
  	dis2 = dis1 + xdf1->nrec + 1;
  
*** ../vim-9.0.1417/src/xdiff/xutils.c	2021-09-13 21:14:59.000000000 +0100
--- src/xdiff/xutils.c	2023-03-20 17:20:10.115087425 +0000
***************
*** 122,128 ****
  	long nl = 0, size, tsize = 0;
  	char const *data, *cur, *top;
  
! 	if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
  		for (top = data + size; nl < sample && cur < top; ) {
  			nl++;
  			if (!(cur = memchr(cur, '\n', top - cur)))
--- 122,128 ----
  	long nl = 0, size, tsize = 0;
  	char const *data, *cur, *top;
  
! 	if ((cur = data = xdl_mmfile_first(mf, &size))) {
  		for (top = data + size; nl < sample && cur < top; ) {
  			nl++;
  			if (!(cur = memchr(cur, '\n', top - cur)))
***************
*** 432,434 ****
--- 432,451 ----
  
  	return 0;
  }
+ 
+ void* xdl_alloc_grow_helper(void *p, long nr, long *alloc, size_t size)
+ {
+ 	void *tmp = NULL;
+ 	size_t n = ((LONG_MAX - 16) / 2 >= *alloc) ? 2 * *alloc + 16 : LONG_MAX;
+ 	if (nr > (long)n)
+ 		n = nr;
+ 	if (SIZE_MAX / size >= n)
+ 		tmp = xdl_realloc(p, n * size);
+ 	if (tmp) {
+ 		*alloc = n;
+ 	} else {
+ 		xdl_free(p);
+ 		*alloc = 0;
+ 	}
+ 	return tmp;
+ }
*** ../vim-9.0.1417/src/xdiff/xutils.h	2021-08-31 19:27:29.000000000 +0100
--- src/xdiff/xutils.h	2023-03-20 17:20:10.115087425 +0000
***************
*** 42,47 ****
  int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
  		       int line1, int count1, int line2, int count2);
  
! 
  
  #endif /* #if !defined(XUTILS_H) */
--- 42,48 ----
  int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
  		       int line1, int count1, int line2, int count2);
  
! /* Do not call this function, use XDL_ALLOC_GROW instead */
! void* xdl_alloc_grow_helper(void* p, long nr, long* alloc, size_t size);
  
  #endif /* #if !defined(XUTILS_H) */
*** ../vim-9.0.1417/src/version.c	2023-03-19 21:57:03.665960580 +0000
--- src/version.c	2023-03-20 17:21:51.443107455 +0000
***************
*** 697,698 ****
--- 697,700 ----
  {   /* Add new patch number below this line */
+ /**/
+     1418,
  /**/

-- 
A successful man is one who makes more money than his wife can spend.
A successful woman is one who can find such a man.

 /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net   \\\
///                                                                      \\\
\\\        sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ ///
 \\\            help me help AIDS victims -- http://ICCF-Holland.org    ///