diff options
| -rw-r--r-- | Documentation/diff-config.txt | 7 | ||||
| -rw-r--r-- | Documentation/diff-options.txt | 9 | ||||
| -rw-r--r-- | diff.c | 23 | ||||
| -rwxr-xr-x | git-add--interactive.perl | 5 | ||||
| -rwxr-xr-x | t/t4061-diff-indent.sh | 187 | ||||
| -rw-r--r-- | xdiff/xdiff.h | 1 | ||||
| -rw-r--r-- | xdiff/xdiffi.c | 325 |
7 files changed, 546 insertions, 11 deletions
diff --git a/Documentation/diff-config.txt b/Documentation/diff-config.txt index f1101c7b21..ad368acda6 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 d9ae681d8f..3a07f6f475 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 @@ -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")) { @@ -3283,7 +3292,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; @@ -3805,9 +3816,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 642cce1ac6..ee3d812695 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/t/t4061-diff-indent.sh b/t/t4061-diff-indent.sh new file mode 100755 index 0000000000..0a65b585af --- /dev/null +++ b/t/t4061-diff-indent.sh @@ -0,0 +1,187 @@ +#!/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 'prepare' ' + cat <<-\EOF >spaces.txt && + 1 + 2 + a + + b + 3 + 4 + EOF + + cat <<-\EOF >functions.c && + 1 + 2 + /* function */ + foo() { + foo + } + + 3 + 4 + EOF + + git add spaces.txt functions.c && + test_tick && + git commit -m initial && + git branch old && + + cat <<-\EOF >spaces.txt && + 1 + 2 + a + + b + a + + b + 3 + 4 + EOF + + cat <<-\EOF >functions.c && + 1 + 2 + /* function */ + bar() { + foo + } + + /* function */ + foo() { + foo + } + + 3 + 4 + EOF + + git add spaces.txt functions.c && + test_tick && + git commit -m initial && + git branch new && + + tr "_" " " <<-\EOF >spaces-expect && + diff --git a/spaces.txt b/spaces.txt + --- a/spaces.txt + +++ b/spaces.txt + @@ -3,5 +3,8 @@ + a + _ + b + +a + + + +b + 3 + 4 + EOF + + tr "_" " " <<-\EOF >spaces-compacted-expect && + diff --git a/spaces.txt b/spaces.txt + --- a/spaces.txt + +++ b/spaces.txt + @@ -2,6 +2,9 @@ + 2 + a + _ + +b + +a + + + b + 3 + 4 + EOF + + tr "_" " " <<-\EOF >functions-expect && + diff --git a/functions.c b/functions.c + --- a/functions.c + +++ b/functions.c + @@ -1,6 +1,11 @@ + 1 + 2 + /* function */ + +bar() { + + foo + +} + + + +/* function */ + foo() { + foo + } + EOF + + tr "_" " " <<-\EOF >functions-compacted-expect + diff --git a/functions.c b/functions.c + --- a/functions.c + +++ b/functions.c + @@ -1,5 +1,10 @@ + 1 + 2 + +/* function */ + +bar() { + + foo + +} + + + /* function */ + foo() { + foo + EOF +' + +test_expect_success 'diff: ugly spaces' ' + git diff old new -- spaces.txt >out && + compare_diff spaces-expect out +' + +test_expect_success 'diff: nice spaces with --indent-heuristic' ' + git diff --indent-heuristic old new -- spaces.txt >out-compacted && + compare_diff spaces-compacted-expect out-compacted +' + +test_expect_success 'diff: nice spaces with diff.indentHeuristic' ' + git -c diff.indentHeuristic=true diff old new -- spaces.txt >out-compacted2 && + compare_diff spaces-compacted-expect out-compacted2 +' + +test_expect_success 'diff: --no-indent-heuristic overrides config' ' + git -c diff.indentHeuristic=true diff --no-indent-heuristic old new -- spaces.txt >out2 && + compare_diff spaces-expect out2 +' + +test_expect_success 'diff: --indent-heuristic with --patience' ' + git diff --indent-heuristic --patience old new -- spaces.txt >out-compacted3 && + compare_diff spaces-compacted-expect out-compacted3 +' + +test_expect_success 'diff: --indent-heuristic with --histogram' ' + git diff --indent-heuristic --histogram old new -- spaces.txt >out-compacted4 && + compare_diff spaces-compacted-expect out-compacted4 +' + +test_expect_success 'diff: ugly functions' ' + git diff old new -- functions.c >out && + compare_diff functions-expect out +' + +test_expect_success 'diff: nice functions with --indent-heuristic' ' + git diff --indent-heuristic old new -- functions.c >out-compacted && + compare_diff functions-compacted-expect out-compacted +' + +test_done diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index 7423f77fc8..8db16d4ae6 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 44fded6723..67c1cccf08 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; + } + } +} + +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 @@ -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: |