v2, 7 partsxdl_change_compact(): only use heuristic if group can't be matched

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 95b037e..61deed8 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -504,25 +504,25 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			}
 		} while (grpsiz != ix - ixs);
 
-		/*
-		 * Try to move back the possibly merged group of changes, to match
-		 * the recorded position in the other file.
-		 */
-		while (ixref < ix) {
-			rchg[--ixs] = 1;
-			rchg[--ix] = 0;
-			while (rchgo[--ixo]);
-		}
-
-		/*
-		 * If a group can be moved back and forth, see if there is a
-		 * blank line in the moving space. If there is a blank line,
-		 * make sure the last blank line is the end of the group.
-		 *
-		 * As we already shifted the group forward as far as possible
-		 * in the earlier loop, we need to shift it back only if at all.
-		 */
-		if ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) {
+		if (ixref < ix) {
+			/*
+			 * Try to move back the possibly merged group of changes, to match
+			 * the recorded position in the other file.
+			 */
+			while (ixref < ix) {
+				rchg[--ixs] = 1;
+				rchg[--ix] = 0;
+				while (rchgo[--ixo]);
+			}
+		} else if ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) {
+			/*
+			 * The group can be slid up to make its last line a
+			 * blank line. Do so.
+			 *
+			 * As we already shifted the group forward as far as
+			 * possible in the earlier loop, we need to shift it
+			 * back only if at all.
+			 */
 			while (ixs > 0 &&
 			       !is_blank_line(recs, ix - 1, flags) &&
 			       recs_match(recs, ixs - 1, ix - 1, flags)) {

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index b3c6848..95b037e 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -528,6 +528,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			       recs_match(recs, ixs - 1, ix - 1, flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
+				while (rchgo[--ixo]);
 			}
 		}
 	}

Documentation/diff-config.txt, Documentation/diff-options.txt, diff.c, git-add--interactive.perl, xdiff/xdiff.h, xdiff/xdiffi.c

diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt
index d5a5b17..c32bd85 100644
--- a/Documentation/diff-config.txt
+++ b/Documentation/diff-config.txt
@@ -170,10 +170,11 @@ diff.tool::
 
 include::mergetools-diff.txt[]
 
+diff.indentHeuristic::
 diff.compactionHeuristic::
-	Set this option to `true` to enable an experimental heuristic that
-	shifts the hunk boundary in an attempt to make the resulting
-	patch easier to read.
+	Set one of these options to `true` to enable one of two
+	experimental heuristics that shift diff hunk boundaries to
+	make patches easier to read.
 
 diff.algorithm::
 	Choose a diff algorithm.  The variants are as follows:
diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index 705a873..ffc2b60 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt
@@ -63,12 +63,13 @@ ifndef::git-format-patch[]
 	Synonym for `-p --raw`.
 endif::git-format-patch[]
 
+--indent-heuristic::
+--no-indent-heuristic::
 --compaction-heuristic::
 --no-compaction-heuristic::
-	These are to help debugging and tuning an experimental
-	heuristic (which is off by default) that shifts the hunk
-	boundary in an attempt to make the resulting patch easier
-	to read.
+	These are to help debugging and tuning experimental heuristics
+	(which are off by default) that shift diff hunk boundaries to
+	make patches easier to read.
 
 --minimal::
 	Spend extra time to make sure the smallest possible
diff --git a/diff.c b/diff.c
index 534c12e..8b15ed7 100644
--- a/diff.c
+++ b/diff.c
@@ -26,6 +26,7 @@
 #endif
 
 static int diff_detect_rename_default;
+static int diff_indent_heuristic; /* experimental */
 static int diff_compaction_heuristic; /* experimental */
 static int diff_rename_limit_default = 400;
 static int diff_suppress_blank_empty;
@@ -190,8 +191,16 @@ int git_diff_ui_config(const char *var, const char *value, void *cb)
 		diff_detect_rename_default = git_config_rename(var, value);
 		return 0;
 	}
+	if (!strcmp(var, "diff.indentheuristic")) {
+		diff_indent_heuristic = git_config_bool(var, value);
+		if (diff_indent_heuristic)
+			diff_compaction_heuristic = 0;
+		return 0;
+	}
 	if (!strcmp(var, "diff.compactionheuristic")) {
 		diff_compaction_heuristic = git_config_bool(var, value);
+		if (diff_compaction_heuristic)
+			diff_indent_heuristic = 0;
 		return 0;
 	}
 	if (!strcmp(var, "diff.autorefreshindex")) {
@@ -3293,7 +3302,9 @@ void diff_setup(struct diff_options *options)
 	options->use_color = diff_use_color_default;
 	options->detect_rename = diff_detect_rename_default;
 	options->xdl_opts |= diff_algorithm;
-	if (diff_compaction_heuristic)
+	if (diff_indent_heuristic)
+		DIFF_XDL_SET(options, INDENT_HEURISTIC);
+	else if (diff_compaction_heuristic)
 		DIFF_XDL_SET(options, COMPACTION_HEURISTIC);
 
 	options->orderfile = diff_order_file_cfg;
@@ -3815,9 +3826,15 @@ int diff_opt_parse(struct diff_options *options,
 		DIFF_XDL_SET(options, IGNORE_WHITESPACE_AT_EOL);
 	else if (!strcmp(arg, "--ignore-blank-lines"))
 		DIFF_XDL_SET(options, IGNORE_BLANK_LINES);
-	else if (!strcmp(arg, "--compaction-heuristic"))
+	else if (!strcmp(arg, "--indent-heuristic")) {
+		DIFF_XDL_SET(options, INDENT_HEURISTIC);
+		DIFF_XDL_CLR(options, COMPACTION_HEURISTIC);
+	} else if (!strcmp(arg, "--no-indent-heuristic"))
+		DIFF_XDL_CLR(options, INDENT_HEURISTIC);
+	else if (!strcmp(arg, "--compaction-heuristic")) {
 		DIFF_XDL_SET(options, COMPACTION_HEURISTIC);
-	else if (!strcmp(arg, "--no-compaction-heuristic"))
+		DIFF_XDL_CLR(options, INDENT_HEURISTIC);
+	} else if (!strcmp(arg, "--no-compaction-heuristic"))
 		DIFF_XDL_CLR(options, COMPACTION_HEURISTIC);
 	else if (!strcmp(arg, "--patience"))
 		options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);
diff --git a/git-add--interactive.perl b/git-add--interactive.perl
index 642cce1..ee3d812 100755
--- a/git-add--interactive.perl
+++ b/git-add--interactive.perl
@@ -45,6 +45,7 @@ my ($diff_new_color) =
 my $normal_color = $repo->get_color("", "reset");
 
 my $diff_algorithm = $repo->config('diff.algorithm');
+my $diff_indent_heuristic = $repo->config_bool('diff.indentheuristic');
 my $diff_compaction_heuristic = $repo->config_bool('diff.compactionheuristic');
 my $diff_filter = $repo->config('interactive.difffilter');
 
@@ -750,7 +751,9 @@ sub parse_diff {
 	if (defined $diff_algorithm) {
 		splice @diff_cmd, 1, 0, "--diff-algorithm=${diff_algorithm}";
 	}
-	if ($diff_compaction_heuristic) {
+	if ($diff_indent_heuristic) {
+		splice @diff_cmd, 1, 0, "--indent-heuristic";
+	} elsif ($diff_compaction_heuristic) {
 		splice @diff_cmd, 1, 0, "--compaction-heuristic";
 	}
 	if (defined $patch_mode_revision) {
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
index 7423f77..8db16d4 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h
@@ -42,6 +42,7 @@ extern "C" {
 #define XDF_IGNORE_BLANK_LINES (1 << 7)
 
 #define XDF_COMPACTION_HEURISTIC (1 << 8)
+#define XDF_INDENT_HEURISTIC (1 << 9)
 
 #define XDL_EMIT_FUNCNAMES (1 << 0)
 #define XDL_EMIT_FUNCCONTEXT (1 << 2)
diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 44fded6..dc79628 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -414,6 +414,286 @@ static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags)
 }
 
 /*
+ * If a line is indented more than this, get_indent() just returns this value.
+ * This avoids having to do absurd amounts of work for data that are not
+ * human-readable text, and also ensures that the output of get_indent fits within
+ * an int.
+ */
+#define MAX_INDENT 200
+
+/*
+ * Return the amount of indentation of the specified line, treating TAB as 8
+ * columns. Return -1 if line is empty or contains only whitespace. Clamp the
+ * output value at MAX_INDENT.
+ */
+static int get_indent(xrecord_t *rec)
+{
+	long i;
+	int ret = 0;
+
+	for (i = 0; i < rec->size; i++) {
+		char c = rec->ptr[i];
+
+		if (!XDL_ISSPACE(c))
+			return ret;
+		else if (c == ' ')
+			ret += 1;
+		else if (c == '\t')
+			ret += 8 - ret % 8;
+		/* ignore other whitespace characters */
+
+		if (ret >= MAX_INDENT)
+			return MAX_INDENT;
+	}
+
+	/* The line contains only whitespace. */
+	return -1;
+}
+
+/*
+ * If more than this number of consecutive blank rows are found, just return this
+ * value. This avoids requiring O(N^2) work for pathological cases, and also
+ * ensures that the output of score_split fits in an int.
+ */
+#define MAX_BLANKS 20
+
+/* Characteristics measured about a hypothetical split position. */
+struct split_measurement {
+	/*
+	 * Is the split at the end of the file (aside from any blank lines)?
+	 */
+	int end_of_file;
+
+	/*
+	 * How much is the line immediately following the split indented (or -1 if
+	 * the line is blank):
+	 */
+	int indent;
+
+	/*
+	 * How many consecutive lines above the split are blank?
+	 */
+	int pre_blank;
+
+	/*
+	 * How much is the nearest non-blank line above the split indented (or -1
+	 * if there is no such line)?
+	 */
+	int pre_indent;
+
+	/*
+	 * How many lines after the line following the split are blank?
+	 */
+	int post_blank;
+
+	/*
+	 * How much is the nearest non-blank line after the line following the
+	 * split indented (or -1 if there is no such line)?
+	 */
+	int post_indent;
+};
+
+struct split_score {
+	/* The effective indent of this split (smaller is preferred). */
+	int effective_indent;
+
+	/* Penalty for this split (smaller is preferred). */
+	int penalty;
+};
+
+/*
+ * Fill m with information about a hypothetical split of xdf above line split.
+ */
+static void measure_split(const xdfile_t *xdf, long split,
+			  struct split_measurement *m)
+{
+	long i;
+
+	if (split >= xdf->nrec) {
+		m->end_of_file = 1;
+		m->indent = -1;
+	} else {
+		m->end_of_file = 0;
+		m->indent = get_indent(xdf->recs[split]);
+	}
+
+	m->pre_blank = 0;
+	m->pre_indent = -1;
+	for (i = split - 1; i >= 0; i--) {
+		m->pre_indent = get_indent(xdf->recs[i]);
+		if (m->pre_indent != -1)
+			break;
+		m->pre_blank += 1;
+		if (m->pre_blank == MAX_BLANKS) {
+			m->pre_indent = 0;
+			break;
+		}
+	}
+
+	m->post_blank = 0;
+	m->post_indent = -1;
+	for (i = split + 1; i < xdf->nrec; i++) {
+		m->post_indent = get_indent(xdf->recs[i]);
+		if (m->post_indent != -1)
+			break;
+		m->post_blank += 1;
+		if (m->post_blank == MAX_BLANKS) {
+			m->post_indent = 0;
+			break;
+		}
+	}
+}
+
+/*
+ * The empirically-determined weight factors used by score_split() below.
+ * Larger values means that the position is a less favorable place to split.
+ *
+ * Note that scores are only ever compared against each other, so multiplying
+ * all of these weight/penalty values by the same factor wouldn't change the
+ * heuristic's behavior. Still, we need to set that arbitrary scale *somehow*.
+ * In practice, these numbers are chosen to be large enough that they can be
+ * adjusted relative to each other with sufficient precision despite using
+ * integer math.
+ */
+
+/* Penalty if there are no non-blank lines before the split */
+#define START_OF_FILE_PENALTY 1
+
+/* Penalty if there are no non-blank lines after the split */
+#define END_OF_FILE_PENALTY 21
+
+/* Multiplier for the number of blank lines around the split */
+#define TOTAL_BLANK_WEIGHT (-30)
+
+/* Multiplier for the number of blank lines after the split */
+#define POST_BLANK_WEIGHT 6
+
+/*
+ * Penalties applied if the line is indented more than its predecessor
+ */
+#define RELATIVE_INDENT_PENALTY (-4)
+#define RELATIVE_INDENT_WITH_BLANK_PENALTY 10
+
+/*
+ * Penalties applied if the line is indented less than both its predecessor and
+ * its successor
+ */
+#define RELATIVE_OUTDENT_PENALTY 24
+#define RELATIVE_OUTDENT_WITH_BLANK_PENALTY 17
+
+/*
+ * Penalties applied if the line is indented less than its predecessor but not
+ * less than its successor
+ */
+#define RELATIVE_DEDENT_PENALTY 23
+#define RELATIVE_DEDENT_WITH_BLANK_PENALTY 17
+
+/*
+ * We only consider whether the sum of the effective indents for splits are
+ * less than (-1), equal to (0), or greater than (+1) each other. The resulting
+ * value is multiplied by the following weight and combined with the penalty to
+ * determine the better of two scores.
+ */
+#define INDENT_WEIGHT 60
+
+/*
+ * Compute a badness score for the hypothetical split whose measurements are
+ * stored in m. The weight factors were determined empirically using the tools and
+ * corpus described in
+ *
+ *     https://github.com/mhagger/diff-slider-tools
+ *
+ * Also see that project if you want to improve the weights based on, for example,
+ * a larger or more diverse corpus.
+ */
+static void score_add_split(const struct split_measurement *m, struct split_score *s)
+{
+	/*
+	 * A place to accumulate penalty factors (positive makes this index more
+	 * favored):
+	 */
+	int post_blank, total_blank, indent, any_blanks;
+
+	if (m->pre_indent == -1 && m->pre_blank == 0)
+		s->penalty += START_OF_FILE_PENALTY;
+
+	if (m->end_of_file)
+		s->penalty += END_OF_FILE_PENALTY;
+
+	/*
+	 * Set post_blank to the number of blank lines following the split,
+	 * including the line immediately after the split:
+	 */
+	post_blank = (m->indent == -1) ? 1 + m->post_blank : 0;
+	total_blank = m->pre_blank + post_blank;
+
+	/* Penalties based on nearby blank lines: */
+	s->penalty += TOTAL_BLANK_WEIGHT * total_blank;
+	s->penalty += POST_BLANK_WEIGHT * post_blank;
+
+	if (m->indent != -1)
+		indent = m->indent;
+	else
+		indent = m->post_indent;
+
+	any_blanks = (total_blank != 0);
+
+	/* Note that the effective indent is -1 at the end of the file: */
+	s->effective_indent += indent;
+
+	if (indent == -1) {
+		/* No additional adjustments needed. */
+	} else if (m->pre_indent == -1) {
+		/* No additional adjustments needed. */
+	} else if (indent > m->pre_indent) {
+		/*
+		 * The line is indented more than its predecessor.
+		 */
+		s->penalty += any_blanks ?
+			RELATIVE_INDENT_WITH_BLANK_PENALTY :
+			RELATIVE_INDENT_PENALTY;
+	} else if (indent == m->pre_indent) {
+		/*
+		 * The line has the same indentation level as its predecessor.
+		 * No additional adjustments needed.
+		 */
+	} else {
+		/*
+		 * The line is indented less than its predecessor. It could be
+		 * the block terminator of the previous block, but it could
+		 * also be the start of a new block (e.g., an "else" block, or
+		 * maybe the previous block didn't have a block terminator).
+		 * Try to distinguish those cases based on what comes next:
+		 */
+		if (m->post_indent != -1 && m->post_indent > indent) {
+			/*
+			 * The following line is indented more. So it is likely
+			 * that this line is the start of a block.
+			 */
+			s->penalty += any_blanks ?
+				RELATIVE_OUTDENT_WITH_BLANK_PENALTY :
+				RELATIVE_OUTDENT_PENALTY;
+		} else {
+			/*
+			 * That was probably the end of a block.
+			 */
+			s->penalty += any_blanks ?
+				RELATIVE_DEDENT_WITH_BLANK_PENALTY :
+				RELATIVE_DEDENT_PENALTY;
+		}
+	}
+}
+
+int score_cmp(struct split_score *s1, struct split_score *s2)
+{
+	/* -1 if s1.effective_indent < s2->effective_indent, etc. */
+	int cmp_indents = ((s1->effective_indent > s2->effective_indent) -
+			   (s1->effective_indent < s2->effective_indent));
+
+	return INDENT_WEIGHT * cmp_indents + (s1->penalty - s2->penalty);
+}
+
+/*
  * Represent a group of changed lines in an xdfile_t (i.e., a contiguous group
  * of lines that was inserted or deleted from the corresponding version of the
  * file). We consider there to be such a group at the beginning of the file, at
@@ -604,6 +884,14 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			}
 		} while (groupsize != g.end - g.start);
 
+		/*
+		 * If the group can be shifted, then we can possibly use this
+		 * freedom to produce a more intuitive diff.
+		 *
+		 * The group is currently shifted as far down as possible, so the
+		 * heuristics below only have to handle upwards shifts.
+		 */
+
 		if (g.end == earliest_end) {
 			/* no shifting was possible */
 		} else if (end_matching_other != -1) {
@@ -633,6 +921,43 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 				if (group_previous(xdfo, &go))
 					xdl_bug("group sync broken sliding to blank line");
 			}
+		} else if (flags & XDF_INDENT_HEURISTIC) {
+			/*
+			 * Indent heuristic: a group of pure add/delete lines
+			 * implies two splits, one between the end of the "before"
+			 * context and the start of the group, and another between
+			 * the end of the group and the beginning of the "after"
+			 * context. Some splits are aesthetically better and some
+			 * are worse. We compute a badness "score" for each split,
+			 * and add the scores for the two splits to define a
+			 * "score" for each position that the group can be shifted
+			 * to. Then we pick the shift with the lowest score.
+			 */
+			long shift, best_shift = -1;
+			struct split_score best_score;
+
+			for (shift = earliest_end; shift <= g.end; shift++) {
+				struct split_measurement m;
+				struct split_score score = {0, 0};
+
+				measure_split(xdf, shift, &m);
+				score_add_split(&m, &score);
+				measure_split(xdf, shift - groupsize, &m);
+				score_add_split(&m, &score);
+				if (best_shift == -1 ||
+				    score_cmp(&score, &best_score) <= 0) {
+					best_score.effective_indent = score.effective_indent;
+					best_score.penalty = score.penalty;
+					best_shift = shift;
+				}
+			}
+
+			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");
+			}
 		}
 
 	next:

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 61deed8..ed2df64 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -400,9 +400,9 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 }
 
 
-static int is_blank_line(xrecord_t **recs, long ix, long flags)
+static int is_blank_line(xrecord_t *rec, long flags)
 {
-	return xdl_blankline(recs[ix]->ptr, recs[ix]->size, flags);
+	return xdl_blankline(rec->ptr, rec->size, flags);
 }
 
 static int recs_match(xrecord_t **recs, long ixs, long ix, long flags)
@@ -485,7 +485,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 * the group.
 			 */
 			while (ix < nrec && recs_match(recs, ixs, ix, flags)) {
-				blank_lines += is_blank_line(recs, ix, flags);
+				blank_lines += is_blank_line(recs[ix], flags);
 
 				rchg[ixs++] = 0;
 				rchg[ix++] = 1;
@@ -524,7 +524,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 * back only if at all.
 			 */
 			while (ixs > 0 &&
-			       !is_blank_line(recs, ix - 1, flags) &&
+			       !is_blank_line(recs[ix - 1], flags) &&
 			       recs_match(recs, ixs - 1, ix - 1, flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 8a5832a..44fded6 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -413,126 +413,239 @@ static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags)
 			     flags));
 }
 
-int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
-	long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;
-	char *rchg = xdf->rchg, *rchgo = xdfo->rchg;
-	unsigned int blank_lines;
-	xrecord_t **recs = xdf->recs;
+/*
+ * Represent a group of changed lines in an xdfile_t (i.e., a contiguous group
+ * of lines that was inserted or deleted from the corresponding version of the
+ * file). We consider there to be such a group at the beginning of the file, at
+ * the end of the file, and between any two unchanged lines, though most such
+ * groups will usually be empty.
+ *
+ * If the first line in a group is equal to the line following the group, then
+ * the group can be slid down. Similarly, if the last line in a group is equal
+ * to the line preceding the group, then the group can be slid up. See
+ * group_slide_down() and group_slide_up().
+ *
+ * Note that loops that are testing for changed lines in xdf->rchg do not need
+ * index bounding since the array is prepared with a zero at position -1 and N.
+ */
+struct group {
+	/*
+	 * The index of the first changed line in the group, or the index of
+	 * the unchanged line above which the (empty) group is located.
+	 */
+	long start;
 
 	/*
-	 * This is the same of what GNU diff does. Move back and forward
-	 * change groups for a consistent and pretty diff output. This also
-	 * helps in finding joinable change groups and reduce the diff size.
+	 * The index of the first unchanged line after the group. For an empty
+	 * group, end is equal to start.
 	 */
-	for (ix = ixo = 0;;) {
-		/*
-		 * Find the first changed line in the to-be-compacted file.
-		 * We need to keep track of both indexes, so if we find a
-		 * changed lines group on the other file, while scanning the
-		 * to-be-compacted file, we need to skip it properly. Note
-		 * that loops that are testing for changed lines on rchg* do
-		 * not need index bounding since the array is prepared with
-		 * a zero at position -1 and N.
-		 */
-		for (; ix < nrec && !rchg[ix]; ix++)
-			while (rchgo[ixo++]);
-		if (ix == nrec)
-			break;
+	long end;
+};
+
+/*
+ * Initialize g to point at the first group in xdf.
+ */
+static void group_init(xdfile_t *xdf, struct group *g)
+{
+	g->start = g->end = 0;
+	while (xdf->rchg[g->end])
+		g->end++;
+}
+
+/*
+ * Move g to describe the next (possibly empty) group in xdf and return 0. If g
+ * is already at the end of the file, do nothing and return -1.
+ */
+static inline int group_next(xdfile_t *xdf, struct group *g)
+{
+	if (g->end == xdf->nrec)
+		return -1;
+
+	g->start = g->end + 1;
+	for (g->end = g->start; xdf->rchg[g->end]; g->end++)
+		;
+
+	return 0;
+}
+
+/*
+ * Move g to describe the previous (possibly empty) group in xdf and return 0.
+ * If g is already at the beginning of the file, do nothing and return -1.
+ */
+static inline int group_previous(xdfile_t *xdf, struct group *g)
+{
+	if (g->start == 0)
+		return -1;
+
+	g->end = g->start - 1;
+	for (g->start = g->end; xdf->rchg[g->start - 1]; g->start--)
+		;
+
+	return 0;
+}
+
+/*
+ * If g can be slid toward the end of the file, do so, and if it bumps into a
+ * 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 group *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;
+
+		while (xdf->rchg[g->end])
+			g->end++;
+
+		return 0;
+	} else {
+		return -1;
+	}
+}
+
+/*
+ * If g can be slid toward the beginning of the file, do so, and if it bumps
+ * 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 group *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;
+
+		while (xdf->rchg[g->start - 1])
+			g->start--;
+
+		return 0;
+	} else {
+		return -1;
+	}
+}
+
+static void xdl_bug(const char *msg)
+{
+	fprintf(stderr, "BUG: %s\n", msg);
+	exit(1);
+}
+
+/*
+ * Move back and forward change groups for a consistent and pretty diff output.
+ * This also helps in finding joinable change groups and reducing the diff
+ * size.
+ */
+int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
+	struct group g, go;
+	long earliest_end, end_matching_other;
+	long groupsize;
+	unsigned int blank_lines;
+
+	group_init(xdf, &g);
+	group_init(xdfo, &go);
+
+	while (1) {
+		/* If the group is empty in the to-be-compacted file, skip it: */
+		if (g.end == g.start)
+			goto next;
 
 		/*
-		 * Record the start of a changed-group in the to-be-compacted file
-		 * and find the end of it, on both to-be-compacted and other file
-		 * indexes (ix and ixo).
+		 * Now shift the change up and then down as far as possible in
+		 * each direction. If it bumps into any other changes, merge them.
 		 */
-		ixs = ix;
-		for (ix++; rchg[ix]; ix++);
-		for (; rchgo[ixo]; ixo++);
-
 		do {
-			grpsiz = ix - ixs;
-			blank_lines = 0;
+			groupsize = g.end - g.start;
 
 			/*
-			 * If the line before the current change group, is equal to
-			 * the last line of the current change group, shift backward
-			 * the group.
+			 * Keep track of the last "end" index that causes this
+			 * group to align with a group of changed lines in the
+			 * other file. -1 indicates that we haven't found such
+			 * a match yet:
 			 */
-			while (ixs > 0 && recs_match(recs[ixs - 1], recs[ix - 1], flags)) {
-				rchg[--ixs] = 1;
-				rchg[--ix] = 0;
-
-				/*
-				 * This change might have joined two change groups,
-				 * so we try to take this scenario in account by moving
-				 * the start index accordingly (and so the other-file
-				 * end-of-group index).
-				 */
-				for (; rchg[ixs - 1]; ixs--);
-				while (rchgo[--ixo]);
-			}
+			end_matching_other = -1;
 
 			/*
-			 * Record the end-of-group position in case we are matched
-			 * with a group of changes in the other file (that is, the
-			 * change record before the end-of-group index in the other
-			 * file is set).
+			 * Boolean value that records whether there are any blank
+			 * lines that could be made to be the last line of this
+			 * group.
 			 */
-			ixref = rchgo[ixo - 1] ? ix: nrec;
+			blank_lines = 0;
+
+			/* 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");
 
 			/*
-			 * If the first line of the current change group, is equal to
-			 * the line next of the current change group, shift forward
-			 * the group.
+			 * This is this highest that this group can be shifted.
+			 * Record its end index:
 			 */
-			while (ix < nrec && recs_match(recs[ixs], recs[ix], flags)) {
-				blank_lines += is_blank_line(recs[ix], flags);
-
-				rchg[ixs++] = 0;
-				rchg[ix++] = 1;
-
-				/*
-				 * This change might have joined two change groups,
-				 * so we try to take this scenario in account by moving
-				 * the start index accordingly (and so the other-file
-				 * end-of-group index). Keep tracking the reference
-				 * index in case we are shifting together with a
-				 * corresponding group of changes in the other file.
-				 */
-				for (; rchg[ix]; ix++);
-				while (rchgo[++ixo])
-					ixref = ix;
+			earliest_end = g.end;
+
+			if (go.end > go.start)
+				end_matching_other = g.end;
+
+			/* Now shift the group forward as far as possible: */
+			while (1) {
+				if (!blank_lines)
+					blank_lines = is_blank_line(
+							xdf->recs[g.end - 1],
+							flags);
+
+				if (group_slide_down(xdf, &g, flags))
+					break;
+				if (group_next(xdfo, &go))
+					xdl_bug("group sync broken sliding down");
+
+				if (go.end > go.start)
+					end_matching_other = g.end;
 			}
-		} while (grpsiz != ix - ixs);
+		} while (groupsize != g.end - g.start);
 
-		if (ixref < ix) {
+		if (g.end == earliest_end) {
+			/* no shifting was possible */
+		} else if (end_matching_other != -1) {
 			/*
-			 * Try to move back the possibly merged group of changes, to match
-			 * the recorded position in the other file.
+			 * Move the possibly merged group of changes back to line
+			 * up with the last group of changes from the other file
+			 * that it can align with.
 			 */
-			while (ixref < ix) {
-				rchg[--ixs] = 1;
-				rchg[--ix] = 0;
-				while (rchgo[--ixo]);
+			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");
 			}
 		} else if ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) {
 			/*
-			 * The group can be slid up to make its last line a
-			 * blank line. Do so.
+			 * Compaction heuristic: if it is possible to shift the
+			 * group to make its bottom line a blank line, do so.
 			 *
 			 * As we already shifted the group forward as far as
-			 * possible in the earlier loop, we need to shift it
-			 * back only if at all.
+			 * possible in the earlier loop, we only need to handle
+			 * backward shifts, not forward ones.
 			 */
-			while (ixs > 0 &&
-			       !is_blank_line(recs[ix - 1], flags) &&
-			       recs_match(recs[ixs - 1], recs[ix - 1], flags)) {
-				rchg[--ixs] = 1;
-				rchg[--ix] = 0;
-				while (rchgo[--ixo]);
+			while (!is_blank_line(xdf->recs[g.end - 1], flags)) {
+				if (group_slide_up(xdf, &g, flags))
+					xdl_bug("blank line disappeared");
+				if (group_previous(xdfo, &go))
+					xdl_bug("group sync broken sliding to blank line");
 			}
 		}
+
+	next:
+		/* Move past the just-processed group: */
+		if (group_next(xdf, &g))
+			break;
+		if (group_next(xdfo, &go))
+			xdl_bug("group sync broken moving to next group");
 	}
 
+	if (!group_next(xdfo, &go))
+		xdl_bug("group sync broken at end of file");
+
 	return 0;
 }
 

diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index ed2df64..8a5832a 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -405,11 +405,11 @@ static int is_blank_line(xrecord_t *rec, long flags)
 	return xdl_blankline(rec->ptr, rec->size, flags);
 }
 
-static int recs_match(xrecord_t **recs, long ixs, long ix, long flags)
+static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags)
 {
-	return (recs[ixs]->ha == recs[ix]->ha &&
-		xdl_recmatch(recs[ixs]->ptr, recs[ixs]->size,
-			     recs[ix]->ptr, recs[ix]->size,
+	return (rec1->ha == rec2->ha &&
+		xdl_recmatch(rec1->ptr, rec1->size,
+			     rec2->ptr, rec2->size,
 			     flags));
 }
 
@@ -457,7 +457,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 * the last line of the current change group, shift backward
 			 * the group.
 			 */
-			while (ixs > 0 && recs_match(recs, ixs - 1, ix - 1, flags)) {
+			while (ixs > 0 && recs_match(recs[ixs - 1], recs[ix - 1], flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
 
@@ -484,7 +484,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 * the line next of the current change group, shift forward
 			 * the group.
 			 */
-			while (ix < nrec && recs_match(recs, ixs, ix, flags)) {
+			while (ix < nrec && recs_match(recs[ixs], recs[ix], flags)) {
 				blank_lines += is_blank_line(recs[ix], flags);
 
 				rchg[ixs++] = 0;
@@ -525,7 +525,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
 			 */
 			while (ixs > 0 &&
 			       !is_blank_line(recs[ix - 1], flags) &&
-			       recs_match(recs, ixs - 1, ix - 1, flags)) {
+			       recs_match(recs[ixs - 1], recs[ix - 1], flags)) {
 				rchg[--ixs] = 1;
 				rchg[--ix] = 0;
 				while (rchgo[--ixo]);

builtin/blame.c, t/t4059-diff-indent.sh

diff --git a/builtin/blame.c b/builtin/blame.c
index 7ec7823..cde2d15 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -48,11 +48,12 @@ static int show_root;
 static int reverse;
 static int blank_boundary;
 static int incremental;
-static int xdl_opts;
 static int abbrev = -1;
 static int no_whole_file_rename;
 static int show_progress;
 
+static struct rev_info revs;
+
 static struct date_mode blame_date_mode = { DATE_ISO8601 };
 static size_t blame_date_width;
 
@@ -137,11 +138,12 @@ struct progress_info {
 static int diff_hunks(mmfile_t *file_a, mmfile_t *file_b,
 		      xdl_emit_hunk_consume_func_t hunk_func, void *cb_data)
 {
-	xpparam_t xpp = {0};
+	xpparam_t xpp;
 	xdemitconf_t xecfg = {0};
 	xdemitcb_t ecb = {NULL};
 
-	xpp.flags = xdl_opts;
+	memset(&xpp, 0, sizeof(xpp));
+	xpp.flags = revs.diffopt.xdl_opts;
 	xecfg.hunk_func = hunk_func;
 	ecb.priv = cb_data;
 	return xdi_diff(file_a, file_b, &xpp, &xecfg, &ecb);
@@ -2517,7 +2519,6 @@ static int blame_move_callback(const struct option *option, const char *arg, int
 
 int cmd_blame(int argc, const char **argv, const char *prefix)
 {
-	struct rev_info revs;
 	const char *path;
 	struct scoreboard sb;
 	struct origin *o;
@@ -2548,8 +2549,6 @@ int cmd_blame(int argc, const char **argv, const char *prefix)
 		OPT_BIT('l', NULL, &output_option, N_("Show long commit SHA1 (Default: off)"), OUTPUT_LONG_OBJECT_NAME),
 		OPT_BIT('s', NULL, &output_option, N_("Suppress author name and timestamp (Default: off)"), OUTPUT_NO_AUTHOR),
 		OPT_BIT('e', "show-email", &output_option, N_("Show author email instead of name (Default: off)"), OUTPUT_SHOW_EMAIL),
-		OPT_BIT('w', NULL, &xdl_opts, N_("Ignore whitespace differences"), XDF_IGNORE_WHITESPACE),
-		OPT_BIT(0, "minimal", &xdl_opts, N_("Spend extra cycles to find better match"), XDF_NEED_MINIMAL),
 		OPT_STRING('S', NULL, &revs_file, N_("file"), N_("Use revisions from <file> instead of calling git-rev-list")),
 		OPT_STRING(0, "contents", &contents_from, N_("file"), N_("Use <file>'s contents as the final image")),
 		{ OPTION_CALLBACK, 'C', NULL, &opt, N_("score"), N_("Find line copies within and across files"), PARSE_OPT_OPTARG, blame_copy_callback },
diff --git a/t/t4059-diff-indent.sh b/t/t4059-diff-indent.sh
new file mode 100755
index 0000000..8b6c7ef
--- /dev/null
+++ b/t/t4059-diff-indent.sh
@@ -0,0 +1,160 @@
+#!/bin/sh
+
+test_description='Test diff indent heuristic.
+
+'
+. ./test-lib.sh
+. "$TEST_DIRECTORY"/diff-lib.sh
+
+# Compare two diff outputs. Ignore "index" lines, because we don't
+# care about SHA-1s or file modes.
+compare_diff () {
+	sed -e "/^index /d" <"$1" >.tmp-1
+	sed -e "/^index /d" <"$2" >.tmp-2
+	test_cmp .tmp-1 .tmp-2 && rm -f .tmp-1 .tmp-2
+}
+
+test_expect_success 'diff: favor trailing blank lines' '
+	cat <<-\EOF >old &&
+	1
+	2
+	a
+
+	b
+	3
+	4
+	EOF
+
+	cat <<-\EOF >new &&
+	1
+	2
+	a
+
+	b
+	a
+
+	b
+	3
+	4
+	EOF
+
+	tr "_" " " <<-\EOF >expect &&
+	diff --git a/old b/new
+	--- a/old
+	+++ b/new
+	@@ -3,5 +3,8 @@
+	 a
+	_
+	 b
+	+a
+	+
+	+b
+	 3
+	 4
+	EOF
+
+	tr "_" " " <<-\EOF >expect-compacted &&
+	diff --git a/old b/new
+	--- a/old
+	+++ b/new
+	@@ -2,6 +2,9 @@
+	 2
+	 a
+	_
+	+b
+	+a
+	+
+	 b
+	 3
+	 4
+	EOF
+
+	test_must_fail git diff --no-index old new >out &&
+	compare_diff expect out &&
+
+	test_must_fail git diff --no-index --indent-heuristic old new >out-compacted &&
+	compare_diff expect-compacted out-compacted &&
+
+	test_must_fail git -c diff.indentHeuristic=true diff --no-index old new >out-compacted2 &&
+	compare_diff expect-compacted out-compacted2 &&
+
+	test_must_fail git diff --indent-heuristic --patience --no-index old new >out-compacted3 &&
+	compare_diff expect-compacted out-compacted3 &&
+
+	test_must_fail git diff --indent-heuristic --histogram --no-index old new >out-compacted4 &&
+	compare_diff expect-compacted out-compacted4
+'
+
+test_expect_success 'diff: keep functions together' '
+	cat <<-\EOF >old &&
+	1
+	2
+	/* function */
+	foo() {
+	    foo
+	}
+
+	3
+	4
+	EOF
+
+	cat <<-\EOF >new &&
+	1
+	2
+	/* function */
+	bar() {
+	    foo
+	}
+
+	/* function */
+	foo() {
+	    foo
+	}
+
+	3
+	4
+	EOF
+
+	tr "_" " " <<-\EOF >expect &&
+	diff --git a/old b/new
+	--- a/old
+	+++ b/new
+	@@ -1,6 +1,11 @@
+	 1
+	 2
+	 /* function */
+	+bar() {
+	+    foo
+	+}
+	+
+	+/* function */
+	 foo() {
+	     foo
+	 }
+	EOF
+
+	tr "_" " " <<-\EOF >expect-compacted &&
+	diff --git a/old b/new
+	--- a/old
+	+++ b/new
+	@@ -1,5 +1,10 @@
+	 1
+	 2
+	+/* function */
+	+bar() {
+	+    foo
+	+}
+	+
+	 /* function */
+	 foo() {
+	     foo
+	EOF
+
+	test_must_fail git diff --no-index old new >out &&
+	compare_diff expect out &&
+
+	test_must_fail git diff --no-index --indent-heuristic old new >out-compacted &&
+	compare_diff expect-compacted out-compacted
+'
+
+test_done