Merge remote-tracking branch 'upstream/master' into pks/conditional-includes

6 files changed, 578 insertions, 117 deletions

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index daecc5a84..bbdbfdb74 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -2,7 +2,10 @@ IF(DEBUG_POOL)
 	SET(GIT_DEBUG_POOL 1)
 ENDIF()
 
-SET(LIBGIT2_OBJECTS "")
+# Add the features.h file as a dummy. This is required for Xcode
+# to successfully build the libgit2 library when using only
+# object libraries.
+SET(LIBGIT2_OBJECTS "${CMAKE_CURRENT_BINARY_DIR}/git2/sys/features.h")
 
 # This variable will contain the libraries we need to put into
 # libgit2.pc's Requires.private. That is, what we're linking to or
@@ -15,8 +18,8 @@ SET(LIBGIT2_PC_LIBS "")
 
 SET(LIBGIT2_INCLUDES
 	"${CMAKE_CURRENT_BINARY_DIR}"
-	"${CMAKE_SOURCE_DIR}/src"
-	"${CMAKE_SOURCE_DIR}/include")
+	"${libgit2_SOURCE_DIR}/src"
+	"${libgit2_SOURCE_DIR}/include")
 SET(LIBGIT2_LIBS "")
 SET(LIBGIT2_LIBDIRS "")
 
@@ -126,9 +129,9 @@ IF (WIN32 AND WINHTTP)
 	# Since MinGW does not come with headers or an import library for winhttp,
 	# we have to include a private header and generate our own import library
 	IF (MINGW)
-		ADD_SUBDIRECTORY("${CMAKE_SOURCE_DIR}/deps/winhttp" "${CMAKE_BINARY_DIR}/deps/winhttp")
+		ADD_SUBDIRECTORY("${libgit2_SOURCE_DIR}/deps/winhttp" "${libgit2_BINARY_DIR}/deps/winhttp")
 		LIST(APPEND LIBGIT2_LIBS winhttp)
-		LIST(APPEND LIBGIT2_INCLUDES "${CMAKE_SOURCE_DIR}/deps/winhttp")
+		LIST(APPEND LIBGIT2_INCLUDES "${libgit2_SOURCE_DIR}/deps/winhttp")
 		LIST(APPEND LIBGIT2_LIBDIRS ${LIBWINHTTP_PATH})
 	ELSE()
 		LIST(APPEND LIBGIT2_LIBS "winhttp")
@@ -181,8 +184,8 @@ ENDIF()
 
 # Include POSIX regex when it is required
 IF(WIN32 OR AMIGA OR CMAKE_SYSTEM_NAME MATCHES "(Solaris|SunOS)")
-	ADD_SUBDIRECTORY("${CMAKE_SOURCE_DIR}/deps/regex" "${CMAKE_BINARY_DIR}/deps/regex")
-	LIST(APPEND LIBGIT2_INCLUDES "${CMAKE_SOURCE_DIR}/deps/regex")
+	ADD_SUBDIRECTORY("${libgit2_SOURCE_DIR}/deps/regex" "${libgit2_BINARY_DIR}/deps/regex")
+	LIST(APPEND LIBGIT2_INCLUDES "${libgit2_SOURCE_DIR}/deps/regex")
 	LIST(APPEND LIBGIT2_OBJECTS $<TARGET_OBJECTS:regex>)
 ENDIF()
 
@@ -194,8 +197,8 @@ IF (USE_EXT_HTTP_PARSER AND HTTP_PARSER_FOUND AND HTTP_PARSER_VERSION_MAJOR EQUA
 	LIST(APPEND LIBGIT2_PC_LIBS "-lhttp_parser")
 ELSE()
 	MESSAGE(STATUS "http-parser version 2 was not found or disabled; using bundled 3rd-party sources.")
-	ADD_SUBDIRECTORY("${CMAKE_SOURCE_DIR}/deps/http-parser" "${CMAKE_BINARY_DIR}/deps/http-parser")
-	LIST(APPEND LIBGIT2_INCLUDES "${CMAKE_SOURCE_DIR}/deps/http-parser")
+	ADD_SUBDIRECTORY("${libgit2_SOURCE_DIR}/deps/http-parser" "${libgit2_BINARY_DIR}/deps/http-parser")
+	LIST(APPEND LIBGIT2_INCLUDES "${libgit2_SOURCE_DIR}/deps/http-parser")
 	LIST(APPEND LIBGIT2_OBJECTS "$<TARGET_OBJECTS:http-parser>")
 ENDIF()
 
@@ -212,8 +215,8 @@ IF (ZLIB_FOUND)
 	ENDIF()
 ELSE()
 	MESSAGE(STATUS "zlib was not found; using bundled 3rd-party sources." )
-	ADD_SUBDIRECTORY("${CMAKE_SOURCE_DIR}/deps/zlib" "${CMAKE_BINARY_DIR}/deps/zlib")
-	LIST(APPEND LIBGIT2_INCLUDES "${CMAKE_SOURCE_DIR}/deps/zlib")
+	ADD_SUBDIRECTORY("${libgit2_SOURCE_DIR}/deps/zlib" "${libgit2_BINARY_DIR}/deps/zlib")
+	LIST(APPEND LIBGIT2_INCLUDES "${libgit2_SOURCE_DIR}/deps/zlib")
 	LIST(APPEND LIBGIT2_OBJECTS $<TARGET_OBJECTS:zlib>)
 ENDIF()
 
@@ -296,9 +299,9 @@ ADD_DEFINITIONS(-D_FILE_OFFSET_BITS=64)
 
 # Collect sourcefiles
 FILE(GLOB SRC_H
-	"${CMAKE_SOURCE_DIR}/include/git2.h"
-	"${CMAKE_SOURCE_DIR}/include/git2/*.h"
-	"${CMAKE_SOURCE_DIR}/include/git2/sys/*.h")
+	"${libgit2_SOURCE_DIR}/include/git2.h"
+	"${libgit2_SOURCE_DIR}/include/git2/*.h"
+	"${libgit2_SOURCE_DIR}/include/git2/sys/*.h")
 
 # On Windows use specific platform sources
 IF (WIN32 AND NOT CYGWIN)
@@ -343,7 +346,7 @@ IF (${CMAKE_VERSION} VERSION_LESS 2.8.12)
 ELSE()
 	TARGET_INCLUDE_DIRECTORIES(git2internal
 	    PRIVATE ${LIBGIT2_INCLUDES}
-	    PUBLIC ${CMAKE_SOURCE_DIR}/include)
+	    PUBLIC ${libgit2_SOURCE_DIR}/include)
 ENDIF()
 
 SET(LIBGIT2_OBJECTS ${LIBGIT2_OBJECTS} PARENT_SCOPE)
@@ -356,9 +359,9 @@ LINK_DIRECTORIES(${LIBGIT2_LIBDIRS})
 ADD_LIBRARY(git2 ${WIN_RC} ${LIBGIT2_OBJECTS})
 TARGET_LINK_LIBRARIES(git2 ${LIBGIT2_LIBS})
 
-SET_TARGET_PROPERTIES(git2 PROPERTIES LIBRARY_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR})
-SET_TARGET_PROPERTIES(git2 PROPERTIES RUNTIME_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR})
-SET_TARGET_PROPERTIES(git2 PROPERTIES ARCHIVE_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR})
+SET_TARGET_PROPERTIES(git2 PROPERTIES LIBRARY_OUTPUT_DIRECTORY ${libgit2_BINARY_DIR})
+SET_TARGET_PROPERTIES(git2 PROPERTIES RUNTIME_OUTPUT_DIRECTORY ${libgit2_BINARY_DIR})
+SET_TARGET_PROPERTIES(git2 PROPERTIES ARCHIVE_OUTPUT_DIRECTORY ${libgit2_BINARY_DIR})
 
 # Workaround for Cmake bug #0011240 (see http://public.kitware.com/Bug/view.php?id=11240)
 # Win64+MSVC+static libs = linker error
@@ -379,7 +382,7 @@ IF (SONAME)
 	ENDIF()
 ENDIF()
 STRING(REPLACE ";" " " LIBGIT2_PC_LIBS "${LIBGIT2_PC_LIBS}")
-CONFIGURE_FILE(${CMAKE_SOURCE_DIR}/libgit2.pc.in ${CMAKE_BINARY_DIR}/libgit2.pc @ONLY)
+CONFIGURE_FILE(${libgit2_SOURCE_DIR}/libgit2.pc.in ${libgit2_BINARY_DIR}/libgit2.pc @ONLY)
 
 IF (MSVC_IDE)
    # Precompiled headers
@@ -393,6 +396,6 @@ INSTALL(TARGETS git2
 	LIBRARY DESTINATION ${LIB_INSTALL_DIR}
 	ARCHIVE DESTINATION ${LIB_INSTALL_DIR}
 )
-INSTALL(FILES ${CMAKE_BINARY_DIR}/libgit2.pc DESTINATION ${LIB_INSTALL_DIR}/pkgconfig )
-INSTALL(DIRECTORY ${CMAKE_SOURCE_DIR}/include/git2 DESTINATION ${INCLUDE_INSTALL_DIR} )
-INSTALL(FILES ${CMAKE_SOURCE_DIR}/include/git2.h DESTINATION ${INCLUDE_INSTALL_DIR} )
+INSTALL(FILES ${libgit2_BINARY_DIR}/libgit2.pc DESTINATION ${LIB_INSTALL_DIR}/pkgconfig )
+INSTALL(DIRECTORY ${libgit2_SOURCE_DIR}/include/git2 DESTINATION ${INCLUDE_INSTALL_DIR} )
+INSTALL(FILES ${libgit2_SOURCE_DIR}/include/git2.h DESTINATION ${INCLUDE_INSTALL_DIR} )
diff --git a/src/config_file.c b/src/config_file.c
index 6e004ff69..cc4e7b3b7 100644
--- a/src/config_file.c
+++ b/src/config_file.c
@@ -121,7 +121,7 @@ typedef struct {
 } diskfile_readonly_backend;
 
 static int config_read(git_strmap *values, const git_repository *repo, struct config_file *file, git_config_level_t level, int depth);
-static int config_write(diskfile_backend *cfg, const char *key, const regex_t *preg, const char *value);
+static int config_write(diskfile_backend *cfg, const char *orig_key, const char *key, const regex_t *preg, const char *value);
 static char *escape_value(const char *ptr);
 
 int git_config_file__snapshot(git_config_backend **out, diskfile_backend *in);
@@ -515,7 +515,7 @@ static int config_set(git_config_backend *cfg, const char *name, const char *val
 		GITERR_CHECK_ALLOC(esc_value);
 	}
 
-	if ((ret = config_write(b, key, NULL, esc_value)) < 0)
+	if ((ret = config_write(b, name, key, NULL, esc_value)) < 0)
 		goto out;
 
 	ret = config_refresh(cfg);
@@ -593,7 +593,7 @@ static int config_set_multivar(
 	}
 
 	/* If we do have it, set call config_write() and reload */
-	if ((result = config_write(b, key, &preg, value)) < 0)
+	if ((result = config_write(b, name, key, &preg, value)) < 0)
 		goto out;
 
 	result = config_refresh(cfg);
@@ -643,7 +643,7 @@ static int config_delete(git_config_backend *cfg, const char *name)
 		return -1;
 	}
 
-	if ((result = config_write(b, var->entry->name, NULL, NULL)) < 0)
+	if ((result = config_write(b, name, var->entry->name, NULL, NULL)) < 0)
 		return result;
 
 	return config_refresh(cfg);
@@ -684,7 +684,7 @@ static int config_delete_multivar(git_config_backend *cfg, const char *name, con
 		goto out;
 	}
 
-	if ((result = config_write(b, key, &preg, NULL)) < 0)
+	if ((result = config_write(b, name, key, &preg, NULL)) < 0)
 		goto out;
 
 	result = config_refresh(cfg);
@@ -1866,7 +1866,9 @@ struct write_data {
 	git_buf buffered_comment;
 	unsigned int in_section : 1,
 		preg_replaced : 1;
+	const char *orig_section;
 	const char *section;
+	const char *orig_name;
 	const char *name;
 	const regex_t *preg;
 	const char *value;
@@ -1894,7 +1896,7 @@ static int write_value(struct write_data *write_data)
 
 	q = quotes_for_value(write_data->value);
 	result = git_buf_printf(write_data->buf,
-		"\t%s = %s%s%s\n", write_data->name, q, write_data->value, q);
+		"\t%s = %s%s%s\n", write_data->orig_name, q, write_data->value, q);
 
 	/* If we are updating a single name/value, we're done.  Setting `value`
 	 * to `NULL` will prevent us from trying to write it again later (in
@@ -2025,7 +2027,7 @@ static int write_on_eof(
 	if ((!write_data->preg || !write_data->preg_replaced) && write_data->value) {
 		/* write the section header unless we're already in it */
 		if (!current_section || strcmp(current_section, write_data->section))
-			result = write_section(write_data->buf, write_data->section);
+			result = write_section(write_data->buf, write_data->orig_section);
 
 		if (!result)
 			result = write_value(write_data);
@@ -2037,10 +2039,10 @@ static int write_on_eof(
 /*
  * This is pretty much the parsing, except we write out anything we don't have
  */
-static int config_write(diskfile_backend *cfg, const char *key, const regex_t *preg, const char* value)
+static int config_write(diskfile_backend *cfg, const char *orig_key, const char *key, const regex_t *preg, const char* value)
 {
 	int result;
-	char *section, *name, *ldot;
+	char *orig_section, *section, *orig_name, *name, *ldot;
 	git_filebuf file = GIT_FILEBUF_INIT;
 	git_buf buf = GIT_BUF_INIT;
 	struct reader reader;
@@ -2080,18 +2082,27 @@ static int config_write(diskfile_backend *cfg, const char *key, const regex_t *p
 	ldot = strrchr(key, '.');
 	name = ldot + 1;
 	section = git__strndup(key, ldot - key);
+	GITERR_CHECK_ALLOC(section);
+
+	ldot = strrchr(orig_key, '.');
+	orig_name = ldot + 1;
+	orig_section = git__strndup(orig_key, ldot - orig_key);
+	GITERR_CHECK_ALLOC(orig_section);
 
 	write_data.buf = &buf;
 	git_buf_init(&write_data.buffered_comment, 0);
+	write_data.orig_section = orig_section;
 	write_data.section = section;
 	write_data.in_section = 0;
 	write_data.preg_replaced = 0;
+	write_data.orig_name = orig_name;
 	write_data.name = name;
 	write_data.preg = preg;
 	write_data.value = value;
 
 	result = config_parse(&reader, write_on_section, write_on_variable, write_on_comment, write_on_eof, &write_data);
 	git__free(section);
+	git__free(orig_section);
 	git_buf_free(&write_data.buffered_comment);
 
 	if (result < 0) {
diff --git a/src/transports/smart_protocol.c b/src/transports/smart_protocol.c
index d51238f12..aecfece0a 100644
--- a/src/transports/smart_protocol.c
+++ b/src/transports/smart_protocol.c
@@ -273,7 +273,7 @@ static int fetch_setup_walk(git_revwalk **out, git_repository *repo)
 	git_revwalk *walk = NULL;
 	git_strarray refs;
 	unsigned int i;
-	git_reference *ref;
+	git_reference *ref = NULL;
 	int error;
 
 	if ((error = git_reference_list(&refs, repo)) < 0)
@@ -285,6 +285,9 @@ static int fetch_setup_walk(git_revwalk **out, git_repository *repo)
 	git_revwalk_sorting(walk, GIT_SORT_TIME);
 
 	for (i = 0; i < refs.count; ++i) {
+		git_reference_free(ref);
+		ref = NULL;
+
 		/* No tags */
 		if (!git__prefixcmp(refs.strings[i], GIT_REFS_TAGS_DIR))
 			continue;
@@ -297,16 +300,13 @@ static int fetch_setup_walk(git_revwalk **out, git_repository *repo)
 
 		if ((error = git_revwalk_push(walk, git_reference_target(ref))) < 0)
 			goto on_error;
-
-		git_reference_free(ref);
 	}
 
-	git_strarray_free(&refs);
 	*out = walk;
-	return 0;
 
 on_error:
-	git_revwalk_free(walk);
+	if (error)
+		git_revwalk_free(walk);
 	git_reference_free(ref);
 	git_strarray_free(&refs);
 	return error;
diff --git a/src/transports/ssh.c b/src/transports/ssh.c
index 47d328c41..b37299215 100644
--- a/src/transports/ssh.c
+++ b/src/transports/ssh.c
@@ -419,8 +419,10 @@ static int _git_ssh_authenticate_session(
 		}
 	} while (LIBSSH2_ERROR_EAGAIN == rc || LIBSSH2_ERROR_TIMEOUT == rc);
 
-        if (rc == LIBSSH2_ERROR_PASSWORD_EXPIRED || rc == LIBSSH2_ERROR_AUTHENTICATION_FAILED)
-                return GIT_EAUTH;
+	if (rc == LIBSSH2_ERROR_PASSWORD_EXPIRED ||
+		rc == LIBSSH2_ERROR_AUTHENTICATION_FAILED ||
+		rc == LIBSSH2_ERROR_PUBLICKEY_UNVERIFIED)
+			return GIT_EAUTH;
 
 	if (rc != LIBSSH2_ERROR_NONE) {
 		if (!giterr_last())
diff --git a/src/xdiff/xdiff.h b/src/xdiff/xdiff.h
index f08f72e16..b7dc05697 100644
--- a/src/xdiff/xdiff.h
+++ b/src/xdiff/xdiff.h
@@ -43,6 +43,8 @@ extern "C" {
 
 #define XDF_IGNORE_BLANK_LINES (1 << 7)
 
+#define XDF_INDENT_HEURISTIC (1 << 8)
+
 #define XDL_EMIT_FUNCNAMES (1 << 0)
 #define XDL_EMIT_COMMON (1 << 1)
 #define XDL_EMIT_FUNCCONTEXT (1 << 2)
diff --git a/src/xdiff/xdiffi.c b/src/xdiff/xdiffi.c
index f4d01b48c..3e65b6ce5 100644
--- a/src/xdiff/xdiffi.c
+++ b/src/xdiff/xdiffi.c
@@ -31,7 +31,12 @@
 #define XDL_SNAKE_CNT 20
 #define XDL_K_HEUR 4
 
-
+/** Declare a function as always inlined. */
+#if defined(_MSC_VER)
+# define XDL_INLINE(type) static __inline type
+#else
+# define XDL_INLINE(type) static inline type
+#endif
 
 typedef struct s_xdpsplit {
 	long i1, i2;
@@ -404,106 +409,544 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
 }
 
 
-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;
-	xrecord_t **recs = xdf->recs;
+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));
+}
+
+/*
+ * 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 {
 	/*
-	 * 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.
+	 * Is the split at the end of the file (aside from any blank lines)?
 	 */
-	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)
+	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 {
 		/*
-		 * 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).
+		 * 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:
 		 */
-		ixs = ix;
-		for (ix++; rchg[ix]; ix++);
-		for (; rchgo[ixo]; ixo++);
+		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;
+		}
+	}
+}
+
+static 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
+ * 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 xdlgroup {
+	/*
+	 * 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;
+
+	/*
+	 * The index of the first unchanged line after the group. For an empty
+	 * group, end is equal to start.
+	 */
+	long end;
+};
+
+/*
+ * Initialize g to point at the first group in xdf.
+ */
+static void group_init(xdfile_t *xdf, struct xdlgroup *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.
+ */
+XDL_INLINE(int) group_next(xdfile_t *xdf, struct xdlgroup *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.
+ */
+XDL_INLINE(int) group_previous(xdfile_t *xdf, struct xdlgroup *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 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;
+
+		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 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;
+
+		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 xdlgroup g, go;
+	long earliest_end, end_matching_other;
+	long groupsize;
 
+	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;
+
+		/*
+		 * Now shift the change up and then down as far as possible in
+		 * each direction. If it bumps into any other changes, merge them.
+		 */
 		do {
-			grpsiz = ix - ixs;
+			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[ixs - 1]->ha == recs[ix - 1]->ha &&
-			       xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, 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).
-			 */
-			ixref = rchgo[ixo - 1] ? ix: nrec;
+			/* 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[ixs]->ha == recs[ix]->ha &&
-			       xdl_recmatch(recs[ixs]->ptr, recs[ixs]->size, recs[ix]->ptr, recs[ix]->size, 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 (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);
 
 		/*
-		 * Try to move back the possibly merged group of changes, to match
-		 * the recorded position in the other file.
+		 * 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.
 		 */
-		while (ixref < ix) {
-			rchg[--ixs] = 1;
-			rchg[--ix] = 0;
-			while (rchgo[--ixo]);
+
+		if (g.end == earliest_end) {
+			/* no shifting was possible */
+		} else if (end_matching_other != -1) {
+			/*
+			 * 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 (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_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:
+		/* 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;
 }