From: Jacob Keller <jacob.e.keller@intel.com>
To: git@vger.kernel.org
Cc: Stefan Beller <sbeller@google.com>,
Junio C Hamano <gitster@pobox.com>, Jeff King <peff@peff.net>,
Jens Lehmann <Jens.Lehmann@web.de>,
Davide Libenzi <davidel@xmailserver.org>,
Jacob Keller <jacob.keller@gmail.com>
Subject: [RFC PATCH, WAS: "weird diff output?" 0/2] implement better chunk heuristics
Date: Fri, 15 Apr 2016 09:51:39 -0700 [thread overview]
Message-ID: <20160415165141.4712-1-jacob.e.keller@intel.com> (raw)
From: Jacob Keller <jacob.keller@gmail.com>
I took up Stefan's patch, and modified it to resolve a couple issues. I
also tried to implement the suggestions from Junio's review, as well as
the suggestions I had. It appears to produce equivalent output as Jeff's
script. This version is still missing a few things, and it is possible
Stefan is working on a v2 of his own, but I thought I'd submit this.
There's still several TODOs:
* Add some tests
* better name for the heuristic(?)
* better patch description plus documentation
* is_emptyline should be more generic and handle CRLF
Changes since Stefan's v1:
* Added a patch to implement xdl_hash_and_recmatch as Junio suggested.
* Fixed a segfault in Stefan's patch
* Added XDL flag to configure the behavior
* Used an int and counted empty lines via += instead of |=
* Renamed starts_with_emptyline to is_emptyline
* Added diff command line and config options
For reviewer convenience, the interdiff between this and Stefan's version:
diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt
index edba56522bce..cebf82702d2a 100644
--- a/Documentation/diff-config.txt
+++ b/Documentation/diff-config.txt
@@ -170,6 +170,12 @@ diff.tool::
include::mergetools-diff.txt[]
+diff.emptyLineHeuristic::
+ Set this option to true to enable the empty line chunk heuristic when
+ producing diff output. This heuristic will attempt to shift hunks such
+ that a common empty line occurs below the hunk with the rest of the
+ context above it.
+
diff.algorithm::
Choose a diff algorithm. The variants are as follows:
+
diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt
index 4b0318e2ac15..6c1cd8b35584 100644
--- a/Documentation/diff-options.txt
+++ b/Documentation/diff-options.txt
@@ -63,6 +63,12 @@ ifndef::git-format-patch[]
Synonym for `-p --raw`.
endif::git-format-patch[]
+--empty-line-heuristic::
+--no-empty-line-heuristic::
+ When possible, shift common empty lines in diff hunks below the hunk
+ such that the last common empty line for each hunk is below, with the
+ rest of the context above the hunk.
+
--minimal::
Spend extra time to make sure the smallest possible
diff is produced.
diff --git a/diff.c b/diff.c
index 4dfe6609d059..8ab9a492928d 100644
--- a/diff.c
+++ b/diff.c
@@ -26,6 +26,7 @@
#endif
static int diff_detect_rename_default;
+static int diff_empty_line_heuristic = 0;
static int diff_rename_limit_default = 400;
static int diff_suppress_blank_empty;
static int diff_use_color_default = -1;
@@ -189,6 +190,10 @@ 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.emptylineheuristic")) {
+ diff_empty_line_heuristic = git_config_bool(var, value);
+ return 0;
+ }
if (!strcmp(var, "diff.autorefreshindex")) {
diff_auto_refresh_index = git_config_bool(var, value);
return 0;
@@ -3278,6 +3283,8 @@ 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_empty_line_heuristic)
+ DIFF_XDL_SET(options, EMPTY_LINE_HEURISTIC);
options->orderfile = diff_order_file_cfg;
@@ -3798,6 +3805,10 @@ 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, "--empty-line-heuristic"))
+ DIFF_XDL_SET(options, EMPTY_LINE_HEURISTIC);
+ else if (!strcmp(arg, "--no-empty-line-heuristic"))
+ DIFF_XDL_CLR(options, EMPTY_LINE_HEURISTIC);
else if (!strcmp(arg, "--patience"))
options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);
else if (!strcmp(arg, "--histogram"))
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
index 4fb7e79410c2..9195a5c0e958 100644
--- a/xdiff/xdiff.h
+++ b/xdiff/xdiff.h
@@ -41,6 +41,8 @@ extern "C" {
#define XDF_IGNORE_BLANK_LINES (1 << 7)
+#define XDF_EMPTY_LINE_HEURISTIC (1 << 8)
+
#define XDL_EMIT_FUNCNAMES (1 << 0)
#define XDL_EMIT_FUNCCONTEXT (1 << 2)
diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index 5f14beb98049..83984b90f82f 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -400,7 +400,7 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
}
-static int starts_with_emptyline(const char *recs)
+static int is_emptyline(const char *recs)
{
return recs[0] == '\n'; /* CRLF not covered here */
}
@@ -416,7 +416,7 @@ static int xdl_hash_and_recmatch(xrecord_t **recs, long ixs, long ix, long 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 char has_emptyline;
+ unsigned int emptylines;
xrecord_t **recs = xdf->recs;
/*
@@ -450,7 +450,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
do {
grpsiz = ix - ixs;
- has_emptyline = 0;
+ emptylines = 0;
/*
* If the line before the current change group, is equal to
@@ -458,11 +458,11 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
* the group.
*/
while (ixs > 0 && xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
+ emptylines += is_emptyline(recs[ix - 1]->ptr);
+
rchg[--ixs] = 1;
rchg[--ix] = 0;
- has_emptyline |=
- starts_with_emptyline(recs[ix]->ptr);
/*
* This change might have joined two change groups,
* so we try to take this scenario in account by moving
@@ -492,9 +492,6 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
rchg[ixs++] = 0;
rchg[ix++] = 1;
- has_emptyline |=
- starts_with_emptyline(recs[ix]->ptr);
-
/*
* This change might have joined two change groups,
* so we try to take this scenario in account by moving
@@ -527,21 +524,12 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
* As we shifted the group forward as far as possible, we only
* need to shift it back if at all.
*/
- if (has_emptyline) {
- 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) &&
- !starts_with_emptyline(recs[ix - 1]->ptr)) {
+ if ((flags & XDF_EMPTY_LINE_HEURISTIC) && emptylines) {
+ while (ixs > 0 &&
+ !is_emptyline(recs[ix - 1]->ptr) &&
+ xdl_hash_and_recmatch(recs, ixs - 1, ix - 1, flags)) {
rchg[--ixs] = 1;
rchg[--ix] = 0;
-
- /*
- * This change did not join two change groups,
- * as we did that before already, so there is no
- * need to adapt the other-file, i.e.
- * running
- * for (; rchg[ixs - 1]; ixs--);
- * while (rchgo[--ixo]);
- */
}
}
}
Jacob Keller (1):
xdiff: add xdl_hash_and_recmatch helper function
Stefan Beller (1):
xdiff: implement empty line chunk heuristic
Documentation/diff-config.txt | 6 ++++++
Documentation/diff-options.txt | 6 ++++++
diff.c | 11 +++++++++++
xdiff/xdiff.h | 2 ++
xdiff/xdiffi.c | 42 ++++++++++++++++++++++++++++++++++++++----
5 files changed, 63 insertions(+), 4 deletions(-)
--
2.8.1.369.geae769a
next reply other threads:[~2016-04-15 16:51 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-04-15 16:51 Jacob Keller [this message]
2016-04-15 16:51 ` [RFC PATCH, WAS: "weird diff output?" 1/2] xdiff: add xdl_hash_and_recmatch helper function Jacob Keller
2016-04-15 17:25 ` Junio C Hamano
2016-04-15 19:09 ` Jacob Keller
2016-04-15 16:51 ` [RFC PATCH, WAS: "weird diff output?" 2/2] xdiff: implement empty line chunk heuristic Jacob Keller
2016-04-15 19:57 ` Stefan Beller
2016-04-15 20:06 ` Junio C Hamano
2016-04-15 20:17 ` Jacob Keller
2016-04-15 20:30 ` Junio C Hamano
2016-04-15 21:15 ` Jacob Keller
2016-04-15 21:22 ` Jacob Keller
2016-04-15 21:44 ` Junio C Hamano
2016-04-15 21:56 ` Jacob Keller
2016-04-15 20:06 ` Jacob Keller
2016-04-15 17:02 ` [RFC PATCH, WAS: "weird diff output?" 0/2] implement better chunk heuristics Stefan Beller
2016-04-15 17:10 ` Stefan Beller
2016-04-15 17:27 ` Junio C Hamano
2016-04-15 17:33 ` Stefan Beller
2016-04-15 17:48 ` Junio C Hamano
2016-04-15 19:09 ` Jacob Keller
2016-04-15 19:08 ` Jacob Keller
2016-04-15 19:07 ` Jacob Keller
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20160415165141.4712-1-jacob.e.keller@intel.com \
--to=jacob.e.keller@intel.com \
--cc=Jens.Lehmann@web.de \
--cc=davidel@xmailserver.org \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=jacob.keller@gmail.com \
--cc=peff@peff.net \
--cc=sbeller@google.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).