[PATCH v4 0/2] Implement new zdiff3 conflict style

Implement a zealous diff3, or "zdiff3". This new mode is identical to ordinary diff3 except that it allows compaction of common lines between the two sides of history, if those common lines occur at the beginning or end of a conflict hunk.

Changes since v3:

 * More fixes from Phillip.
 * Marked Phillip as the author of the first commit because he's written
   most the code now; gave myself a co-authored-by trailer on that commit.
 * Removed the RFC label since it's now passing our tests.

Changes since v2:

 * Included more fixes from Phillip, and a new testcase

Changes since v1:

 * Included fixes from Phillip (thanks!)
 * Added some testcases

Elijah Newren (1):
  update documentation for new zdiff3 conflictStyle

Phillip Wood (1):
  xdiff: implement a zealous diff3, or "zdiff3"

 Documentation/config/merge.txt         |  9 ++-
 Documentation/git-checkout.txt         |  3 +-
 Documentation/git-merge-file.txt       |  3 +
 Documentation/git-merge.txt            | 32 +++++++--
 Documentation/git-rebase.txt           |  6 +-
 Documentation/git-restore.txt          |  3 +-
 Documentation/git-switch.txt           |  3 +-
 Documentation/technical/rerere.txt     | 10 +--
 builtin/checkout.c                     |  2 +-
 builtin/merge-file.c                   |  2 +
 contrib/completion/git-completion.bash |  6 +-
 t/t6427-diff3-conflict-markers.sh      | 90 ++++++++++++++++++++++++++
 xdiff-interface.c                      |  2 +
 xdiff/xdiff.h                          |  1 +
 xdiff/xmerge.c                         | 63 ++++++++++++++++--
 15 files changed, 205 insertions(+), 30 deletions(-)

base-commit: 4c719308ce59dc70e606f910f40801f2c6051b24
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1036%2Fnewren%2Fzdiff3-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1036/newren/zdiff3-v4
Pull-Request: https://github.com/git/git/pull/1036

Range-diff vs v3:

 1:  798aefbb40a ! 1:  473fae82da1 xdiff: implement a zealous diff3, or "zdiff3"
     @@
       ## Metadata ##
     -Author: Elijah Newren <newren@gmail.com>
     +Author: Phillip Wood <phillip.wood@dunelm.org.uk>
      
       ## Commit message ##
          xdiff: implement a zealous diff3, or "zdiff3"
     @@ Commit message
          definitely was a conflict and it should remain.
      
          Based-on-patch-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>
     -    Co-authored-by: Phillip Wood <phillip.wood123@gmail.com>
     +    Co-authored-by: Elijah Newren <newren@gmail.com>
     +    Signed-off-by: Phillip Wood <phillip.wood123@gmail.com>
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## builtin/merge-file.c ##
     @@ t/t6427-diff3-conflict-markers.sh: test_expect_success 'rebase --apply describes
      +	)
      +}
      +
     -+test_expect_failure 'check zdiff3 markers' '
     ++test_expect_success 'check zdiff3 markers' '
      +	test_setup_zdiff3 &&
      +	(
      +		cd zdiff3 &&
     @@ xdiff/xmerge.c: static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1,
       		if (!dest) {
       			size += marker_size + 1 + needs_cr + marker3_size;
      @@ xdiff/xmerge.c: static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1,
     -  * lines. Try hard to show only these few lines as conflicting.
     -  */
     - static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
     --		xpparam_t const *xpp)
     -+				xpparam_t const *xpp, int style)
     - {
     - 	for (; m; m = m->next) {
     - 		mmfile_t t1, t2;
     -@@ xdiff/xmerge.c: static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
     - 			continue;
     - 		}
     - 		x = xscr;
     -+		if (style == XDL_MERGE_ZEALOUS_DIFF3) {
     -+			int advance1 = xscr->i1, advance2 = xscr->i2;
     -+
     -+			/*
     -+			 * Advance m->i1 and m->i2 so that conflict for sides
     -+			 * 1 and 2 start after common region.  Decrement
     -+			 * m->chg[12] since there are now fewer conflict lines
     -+			 * for those sides.
     -+			 */
     -+			m->i1 += advance1;
     -+			m->i2 += advance2;
     -+			m->chg1 -= advance1;
     -+			m->chg2 -= advance2;
     -+
     -+			/*
     -+			 * Splitting conflicts due to internal common regions
     -+			 * on the two sides would be inappropriate since we
     -+			 * are also showing the merge base and have no
     -+			 * reasonable way to split the merge base text.
     -+			 */
     -+			while (xscr->next)
     -+				xscr = xscr->next;
     + 	return size;
     + }
     + 
     ++static int recmatch(xrecord_t *rec1, xrecord_t *rec2, unsigned long flags)
     ++{
     ++	return xdl_recmatch(rec1->ptr, rec1->size,
     ++			    rec2->ptr, rec2->size, flags);
     ++}
      +
     -+			/*
     -+			 * Lower the number of conflict lines to not include
     -+			 * the final common lines, if any.  Do this by setting
     -+			 * number of conflict lines to
     -+			 *   (line offset for start of conflict in xscr) +
     -+			 *   (number of lines in the conflict in xscr)
     -+			 */
     -+			m->chg1 = (xscr->i1 - advance1) + (xscr->chg1);
     -+			m->chg2 = (xscr->i2 - advance2) + (xscr->chg2);
     -+			xdl_free_env(&xe);
     -+			xdl_free_script(x);
     ++/*
     ++ * Remove any common lines from the beginning and end of the conflicted region.
     ++ */
     ++static void xdl_refine_zdiff3_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
     ++		xpparam_t const *xpp)
     ++{
     ++	xrecord_t **rec1 = xe1->xdf2.recs, **rec2 = xe2->xdf2.recs;
     ++	for (; m; m = m->next) {
     ++		/* let's handle just the conflicts */
     ++		if (m->mode)
      +			continue;
     ++
     ++		while(m->chg1 && m->chg2 &&
     ++		      recmatch(rec1[m->i1], rec2[m->i2], xpp->flags)) {
     ++			m->chg1--;
     ++			m->chg2--;
     ++			m->i1++;
     ++			m->i2++;
      +		}
     - 		m->i1 = xscr->i1 + i1;
     - 		m->chg1 = xscr->chg1;
     - 		m->i2 = xscr->i2 + i2;
     -@@ xdiff/xmerge.c: static int lines_contain_alnum(xdfenv_t *xe, int i, int chg)
     - static void xdl_merge_two_conflicts(xdmerge_t *m)
     - {
     - 	xdmerge_t *next_m = m->next;
     -+	m->chg0 = next_m->i0 + next_m->chg0 - m->i0;
     - 	m->chg1 = next_m->i1 + next_m->chg1 - m->i1;
     - 	m->chg2 = next_m->i2 + next_m->chg2 - m->i2;
     - 	m->next = next_m->next;
     -@@ xdiff/xmerge.c: static void xdl_merge_two_conflicts(xdmerge_t *m)
     -  * it appears simpler -- because it takes up less (or as many) lines --
     -  * if the lines are moved into the conflicts.
     -  */
     --static int xdl_simplify_non_conflicts(xdfenv_t *xe1, xdmerge_t *m,
     -+static int xdl_simplify_non_conflicts(xdfenv_t *xe1, xdmerge_t *m, int style,
     - 				      int simplify_if_no_alnum)
     - {
     - 	int result = 0;
     - 
     --	if (!m)
     -+	if (!m || style == XDL_MERGE_ZEALOUS_DIFF3)
     - 		return result;
     - 	for (;;) {
     - 		xdmerge_t *next_m = m->next;
     ++		while (m->chg1 && m->chg2 &&
     ++		       recmatch(rec1[m->i1 + m->chg1 - 1],
     ++				rec2[m->i2 + m->chg2 - 1], xpp->flags)) {
     ++			m->chg1--;
     ++			m->chg2--;
     ++		}
     ++	}
     ++}
     ++
     + /*
     +  * Sometimes, changes are not quite identical, but differ in only a few
     +  * lines. Try hard to show only these few lines as conflicting.
      @@ xdiff/xmerge.c: static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
       	int style = xmp->style;
       	int favor = xmp->favor;
       
     +-	if (style == XDL_MERGE_DIFF3) {
      +	/*
      +	 * XDL_MERGE_DIFF3 does not attempt to refine conflicts by looking
      +	 * at common areas of sides 1 & 2, because the base (side 0) does
     @@ xdiff/xmerge.c: static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
      +	 * of the conflict block.  Since XDL_MERGE_ZEALOUS_DIFF3's
      +	 * conflict refinement is much more limited in this fashion, the
      +	 * conflict simplification will be skipped.
     -+	 *
     -+	 * See xdl_refine_conflicts() and xdl_simplify_non_conflicts()
     -+	 * for more details, particularly looking for
     -+	 * XDL_MERGE_ZEALOUS_DIFF3.
      +	 */
     - 	if (style == XDL_MERGE_DIFF3) {
     ++	if (style == XDL_MERGE_DIFF3 || style == XDL_MERGE_ZEALOUS_DIFF3) {
       		/*
       		 * "diff3 -m" output does not make sense for anything
     + 		 * more aggressive than XDL_MERGE_EAGER.
      @@ xdiff/xmerge.c: static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
     + 	if (!changes)
       		changes = c;
       	/* refine conflicts */
     - 	if (XDL_MERGE_ZEALOUS <= level &&
     +-	if (XDL_MERGE_ZEALOUS <= level &&
      -	    (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 ||
      -	     xdl_simplify_non_conflicts(xe1, changes,
     -+	    (xdl_refine_conflicts(xe1, xe2, changes, xpp, style) < 0 ||
     -+	     xdl_simplify_non_conflicts(xe1, changes, style,
     - 					XDL_MERGE_ZEALOUS < level) < 0)) {
     +-					XDL_MERGE_ZEALOUS < level) < 0)) {
     ++	if (style == XDL_MERGE_ZEALOUS_DIFF3) {
     ++		xdl_refine_zdiff3_conflicts(xe1, xe2, changes, xpp);
     ++	} else if (XDL_MERGE_ZEALOUS <= level &&
     ++		   (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 ||
     ++		    xdl_simplify_non_conflicts(xe1, changes,
     ++					       XDL_MERGE_ZEALOUS < level) < 0)) {
       		xdl_cleanup_merge(changes);
       		return -1;
     + 	}
 2:  90aee68e14a = 2:  69f20a702b4 update documentation for new zdiff3 conflictStyle