diff options
| -rw-r--r-- | Documentation/diff-options.txt | 10 | ||||
| -rw-r--r-- | diff.c | 22 | ||||
| -rw-r--r-- | diff.h | 4 | ||||
| -rwxr-xr-x | t/t4065-diff-anchored.sh | 94 | ||||
| -rw-r--r-- | xdiff/xdiff.h | 4 | ||||
| -rw-r--r-- | xdiff/xpatience.c | 42 |
6 files changed, 169 insertions, 7 deletions
diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt index 3c93c21683..9d1586b956 100644 --- a/Documentation/diff-options.txt +++ b/Documentation/diff-options.txt @@ -80,6 +80,16 @@ endif::git-format-patch[] --histogram:: Generate a diff using the "histogram diff" algorithm. +--anchored=<text>:: + Generate a diff using the "anchored diff" algorithm. ++ +This option may be specified more than once. ++ +If a line exists in both the source and destination, exists only once, +and starts with this text, this algorithm attempts to prevent it from +appearing as a deletion or addition in the output. It uses the "patience +diff" algorithm internally. + --diff-algorithm={patience|minimal|histogram|myers}:: Choose a diff algorithm. The variants are as follows: + @@ -3210,6 +3210,8 @@ static void builtin_diff(const char *name_a, ecbdata.opt = o; ecbdata.header = header.len ? &header : NULL; xpp.flags = o->xdl_opts; + xpp.anchors = o->anchors; + xpp.anchors_nr = o->anchors_nr; xecfg.ctxlen = o->context; xecfg.interhunkctxlen = o->interhunkcontext; xecfg.flags = XDL_EMIT_FUNCNAMES; @@ -3302,6 +3304,8 @@ static void builtin_diffstat(const char *name_a, const char *name_b, memset(&xpp, 0, sizeof(xpp)); memset(&xecfg, 0, sizeof(xecfg)); xpp.flags = o->xdl_opts; + xpp.anchors = o->anchors; + xpp.anchors_nr = o->anchors_nr; xecfg.ctxlen = o->context; xecfg.interhunkctxlen = o->interhunkcontext; if (xdi_diff_outf(&mf1, &mf2, diffstat_consume, diffstat, @@ -4594,9 +4598,18 @@ int diff_opt_parse(struct diff_options *options, DIFF_XDL_SET(options, INDENT_HEURISTIC); else if (!strcmp(arg, "--no-indent-heuristic")) DIFF_XDL_CLR(options, INDENT_HEURISTIC); - else if (!strcmp(arg, "--patience")) + else if (!strcmp(arg, "--patience")) { + int i; options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF); - else if (!strcmp(arg, "--histogram")) + /* + * Both --patience and --anchored use PATIENCE_DIFF + * internally, so remove any anchors previously + * specified. + */ + for (i = 0; i < options->anchors_nr; i++) + free(options->anchors[i]); + options->anchors_nr = 0; + } else if (!strcmp(arg, "--histogram")) options->xdl_opts = DIFF_WITH_ALG(options, HISTOGRAM_DIFF); else if ((argcount = parse_long_opt("diff-algorithm", av, &optarg))) { long value = parse_algorithm_value(optarg); @@ -4608,6 +4621,11 @@ int diff_opt_parse(struct diff_options *options, options->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK; options->xdl_opts |= value; return argcount; + } else if (skip_prefix(arg, "--anchored=", &arg)) { + options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF); + ALLOC_GROW(options->anchors, options->anchors_nr + 1, + options->anchors_alloc); + options->anchors[options->anchors_nr++] = xstrdup(arg); } /* flags options */ @@ -166,6 +166,10 @@ struct diff_options { const char *stat_sep; long xdl_opts; + /* see Documentation/diff-options.txt */ + char **anchors; + size_t anchors_nr, anchors_alloc; + int stat_width; int stat_name_width; int stat_graph_width; diff --git a/t/t4065-diff-anchored.sh b/t/t4065-diff-anchored.sh new file mode 100755 index 0000000000..b3f510f040 --- /dev/null +++ b/t/t4065-diff-anchored.sh @@ -0,0 +1,94 @@ +#!/bin/sh + +test_description='anchored diff algorithm' + +. ./test-lib.sh + +test_expect_success '--anchored' ' + printf "a\nb\nc\n" >pre && + printf "c\na\nb\n" >post && + + # normally, c is moved to produce the smallest diff + test_expect_code 1 git diff --no-index pre post >diff && + grep "^+c" diff && + + # with anchor, a is moved + test_expect_code 1 git diff --no-index --anchored=c pre post >diff && + grep "^+a" diff +' + +test_expect_success '--anchored multiple' ' + printf "a\nb\nc\nd\ne\nf\n" >pre && + printf "c\na\nb\nf\nd\ne\n" >post && + + # with 1 anchor, c is not moved, but f is moved + test_expect_code 1 git diff --no-index --anchored=c pre post >diff && + grep "^+a" diff && # a is moved instead of c + grep "^+f" diff && + + # with 2 anchors, c and f are not moved + test_expect_code 1 git diff --no-index --anchored=c --anchored=f pre post >diff && + grep "^+a" diff && + grep "^+d" diff # d is moved instead of f +' + +test_expect_success '--anchored with nonexistent line has no effect' ' + printf "a\nb\nc\n" >pre && + printf "c\na\nb\n" >post && + + test_expect_code 1 git diff --no-index --anchored=x pre post >diff && + grep "^+c" diff +' + +test_expect_success '--anchored with non-unique line has no effect' ' + printf "a\nb\nc\nd\ne\nc\n" >pre && + printf "c\na\nb\nc\nd\ne\n" >post && + + test_expect_code 1 git diff --no-index --anchored=c pre post >diff && + grep "^+c" diff +' + +test_expect_success 'diff still produced with impossible multiple --anchored' ' + printf "a\nb\nc\n" >pre && + printf "c\na\nb\n" >post && + + test_expect_code 1 git diff --no-index --anchored=a --anchored=c pre post >diff && + mv post expected_post && + + # Ensure that the diff is correct by applying it and then + # comparing the result with the original + git apply diff && + diff expected_post post +' + +test_expect_success 'later algorithm arguments override earlier ones' ' + printf "a\nb\nc\n" >pre && + printf "c\na\nb\n" >post && + + test_expect_code 1 git diff --no-index --patience --anchored=c pre post >diff && + grep "^+a" diff && + + test_expect_code 1 git diff --no-index --anchored=c --patience pre post >diff && + grep "^+c" diff && + + test_expect_code 1 git diff --no-index --histogram --anchored=c pre post >diff && + grep "^+a" diff && + + test_expect_code 1 git diff --no-index --anchored=c --histogram pre post >diff && + grep "^+c" diff +' + +test_expect_success '--anchored works with other commands like "git show"' ' + printf "a\nb\nc\n" >file && + git add file && + git commit -m foo && + printf "c\na\nb\n" >file && + git add file && + git commit -m foo && + + # with anchor, a is moved + git show --patience --anchored=c >diff && + grep "^+a" diff +' + +test_done diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index 915591f7d4..c1937a2911 100644 --- a/xdiff/xdiff.h +++ b/xdiff/xdiff.h @@ -86,6 +86,10 @@ typedef struct s_mmbuffer { typedef struct s_xpparam { unsigned long flags; + + /* See Documentation/diff-options.txt. */ + char **anchors; + size_t anchors_nr; } xpparam_t; typedef struct s_xdemitcb { diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index a44e776328..f3573d9f00 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -62,6 +62,12 @@ struct hashmap { * initially, "next" reflects only the order in file1. */ struct entry *next, *previous; + + /* + * If 1, this entry can serve as an anchor. See + * Documentation/diff-options.txt for more information. + */ + unsigned anchor : 1; } *entries, *first, *last; /* were common records found? */ unsigned long has_matches; @@ -70,8 +76,19 @@ struct hashmap { xpparam_t const *xpp; }; +static int is_anchor(xpparam_t const *xpp, const char *line) +{ + int i; + for (i = 0; i < xpp->anchors_nr; i++) { + if (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i]))) + return 1; + } + return 0; +} + /* The argument "pass" is 1 for the first file, 2 for the second. */ -static void insert_record(int line, struct hashmap *map, int pass) +static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map, + int pass) { xrecord_t **records = pass == 1 ? map->env->xdf1.recs : map->env->xdf2.recs; @@ -110,6 +127,7 @@ static void insert_record(int line, struct hashmap *map, int pass) return; map->entries[index].line1 = line; map->entries[index].hash = record->ha; + map->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr); if (!map->first) map->first = map->entries + index; if (map->last) { @@ -147,11 +165,11 @@ static int fill_hashmap(mmfile_t *file1, mmfile_t *file2, /* First, fill with entries from the first file */ while (count1--) - insert_record(line1++, result, 1); + insert_record(xpp, line1++, result, 1); /* Then search for matches in the second file */ while (count2--) - insert_record(line2++, result, 2); + insert_record(xpp, line2++, result, 2); return 0; } @@ -192,14 +210,28 @@ static struct entry *find_longest_common_sequence(struct hashmap *map) int longest = 0, i; struct entry *entry; + /* + * If not -1, this entry in sequence must never be overridden. + * Therefore, overriding entries before this has no effect, so + * do not do that either. + */ + int anchor_i = -1; + for (entry = map->first; entry; entry = entry->next) { if (!entry->line2 || entry->line2 == NON_UNIQUE) continue; i = binary_search(sequence, longest, entry); entry->previous = i < 0 ? NULL : sequence[i]; - sequence[++i] = entry; - if (i == longest) + ++i; + if (i <= anchor_i) + continue; + sequence[i] = entry; + if (entry->anchor) { + anchor_i = i; + longest = anchor_i + 1; + } else if (i == longest) { longest++; + } } /* No common unique lines were found */ |