{"thread":{"id":"47286","subject":"[RFC PATCH] xdiff/xpatience: support anchoring a line","startedAt":"2017-11-21T22:17:32Z","lastAt":"2017-12-04T19:45:42Z","messageCount":15,"participants":["Jonathan Tan","Stefan Beller","Junio C Hamano","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"333178","messageId":"20171121221717.155301-1-jonathantanmy@google.com","threadId":"47286","inReplyTo":null,"subject":"[RFC PATCH] xdiff/xpatience: support anchoring a line","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-11-21T22:17:17Z","receivedAt":"2017-11-21T22:17:32Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Teach the patience diff to support prohibiting a user-specified line\nfrom appearing as a deletion or addition in the end result.\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\nI'm sending this out to see if a change similar to this would be\nwelcome. It is useful to me as a reviewer (to check my own code, e.g.\nwhen checking [1]). Probably more design needs to go into this,\nincluding the best way to specify the \"anchor\" line, and the correct\nbehavior when the anchor is either not found or appears more than once.\n\nAny thoughts?\n\n[1]\nhttps://public-inbox.org/git/20171121221256.154741-1-jonathantanmy@google.com/\n---\n t/t4033-diff-patience.sh | 13 +++++++++++++\n xdiff/xpatience.c        | 29 +++++++++++++++++++++++++++--\n 2 files changed, 40 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t4033-diff-patience.sh b/t/t4033-diff-patience.sh\nindex 113304dc5..2147fd688 100755\n--- a/t/t4033-diff-patience.sh\n+++ b/t/t4033-diff-patience.sh\n@@ -13,6 +13,19 @@ test_expect_success '--ignore-space-at-eol with a single appended character' '\n \tgrep \"^+.*X\" diff\n '\n \n+test_expect_success 'anchor' '\n+\tprintf \"a\\nb\\nc\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\n\" >post &&\n+\n+\t# without anchor, c is moved\n+\ttest_expect_code 1 git diff --no-index --patience pre post >diff &&\n+\tgrep \"^+c\" diff &&\n+\n+\t# with anchor, a is moved\n+\tDIFF_ANCHOR=c test_expect_code 1 git diff --no-index --patience pre post >diff &&\n+\tgrep \"^+a\" diff\n+'\n+\n test_diff_frobnitz \"patience\"\n \n test_diff_unique \"patience\"\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex a44e77632..195a60e57 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -62,6 +62,8 @@ struct hashmap {\n \t\t * initially, \"next\" reflects only the order in file1.\n \t\t */\n \t\tstruct entry *next, *previous;\n+\n+\t\tunsigned anchor : 1;\n \t} *entries, *first, *last;\n \t/* were common records found? */\n \tunsigned long has_matches;\n@@ -70,6 +72,14 @@ struct hashmap {\n \txpparam_t const *xpp;\n };\n \n+static int is_anchor(const char *line)\n+{\n+\tchar *anchor = getenv(\"DIFF_ANCHOR\");\n+\tif (!anchor)\n+\t\treturn 0;\n+\treturn !strncmp(line, anchor, strlen(anchor));\n+}\n+\n /* The argument \"pass\" is 1 for the first file, 2 for the second. */\n static void insert_record(int line, struct hashmap *map, int pass)\n {\n@@ -110,6 +120,7 @@ static void insert_record(int line, struct hashmap *map, int pass)\n \t\treturn;\n \tmap->entries[index].line1 = line;\n \tmap->entries[index].hash = record->ha;\n+\tmap->entries[index].anchor = is_anchor(map->env->xdf1.recs[line - 1]->ptr);\n \tif (!map->first)\n \t\tmap->first = map->entries + index;\n \tif (map->last) {\n@@ -192,14 +203,28 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)\n \tint longest = 0, i;\n \tstruct entry *entry;\n \n+\t/*\n+\t * If not -1, this entry in sequence must never be overridden. (Also,\n+\t * do not override entries in sequence before this entry, since it is\n+\t * useless.)\n+\t */\n+\tint anchor_i = -1;\n+\n \tfor (entry = map->first; entry; entry = entry->next) {\n \t\tif (!entry->line2 || entry->line2 == NON_UNIQUE)\n \t\t\tcontinue;\n \t\ti = binary_search(sequence, longest, entry);\n \t\tentry->previous = i < 0 ? NULL : sequence[i];\n-\t\tsequence[++i] = entry;\n-\t\tif (i == longest)\n+\t\t++i;\n+\t\tif (i <= anchor_i)\n+\t\t\tcontinue;\n+\t\tsequence[i] = entry;\n+\t\tif (anchor_i == -1 && entry->anchor) {\n+\t\t\tanchor_i = i;\n+\t\t\tlongest = anchor_i + 1;\n+\t\t} else if (i == longest) {\n \t\t\tlongest++;\n+\t\t}\n \t}\n \n \t/* No common unique lines were found */\n-- \n2.15.0.448.gf294e3d99a-goog\n\n"},{"id":"333192","messageId":"CAGZ79kba49xP8m2gf-BAGkUhJ_=qwwr6LVJohbA+afFhjOn49w@mail.gmail.com","threadId":"47286","inReplyTo":"20171121221717.155301-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] xdiff/xpatience: support anchoring a line","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-11-21T23:28:43Z","receivedAt":"2017-11-21T23:28:50Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Nov 21, 2017 at 2:17 PM, Jonathan Tan <jonathantanmy@google.com> wrote:\n> Teach the patience diff to support prohibiting a user-specified line\n> from appearing as a deletion or addition in the end result.\n>\n> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>\n> ---\n> I'm sending this out to see if a change similar to this would be\n> welcome. It is useful to me as a reviewer (to check my own code, e.g.\n> when checking [1]). Probably more design needs to go into this,\n> including the best way to specify the \"anchor\" line, and the correct\n> behavior when the anchor is either not found or appears more than once.\n>\n> Any thoughts?\n\nThe background from this whole idea is that the Myers diff algorithm\nmay produce the shortest diff, which is good for computer consumption\nor transport, but not ideal for human review. To accommodate human\nreview we need to couple the diff with higher level concepts, such as\nmove detection or ignoring blanks.\n\nI would imagine that this anchor can be set by a user to a function\nheader or other significant line, such that the commit is more in line with\nthe diff itself (\"move code out of function A into its helper\" would not\nwant to have the \"function A\" line jump around, but the code should\nbe removed from the function, hence you'd anchor the function).\n\nThe solution you provide is a good thing to experiment with, but\nlonger term, I would want to have huge record of configs in which\nhumans selected the best diff, such that we can use that data\nto reason about better automatic diff generation.\nThe diff heuristic was based on a lot of human generated data,\nthat was generated by Michael at the time. I wonder if we want to\npermanently store the anchor so the data collection will happen\nautomatically over time.\n\nI had a similar idea, which would affix a given coordinate of the map[1]\nto be on the path. I imagine it similar to e.g. Google Maps in which you\ncan select intermittent way points on your route.\n\nWhen having this rather abstract coordinate, which can be\ngiven as line number in pre and post image, then we would not\nneed to think about questions whether a given line is found or\nappears multiple times; however users like concise input the best,\nso the idea of an \"anchor line\" might be the best representation for\nthe user, which is internally translated into way points.\n\n[1] think of http://simplygenius.net/ArticleFiles/DiffTutorial/diagonals.png\n\nStefan\n\n> [1]\n> https://public-inbox.org/git/20171121221256.154741-1-jonathantanmy@google.com/\n> ---\n>  t/t4033-diff-patience.sh | 13 +++++++++++++\n>  xdiff/xpatience.c        | 29 +++++++++++++++++++++++++++--\n>  2 files changed, 40 insertions(+), 2 deletions(-)\n>\n> diff --git a/t/t4033-diff-patience.sh b/t/t4033-diff-patience.sh\n> index 113304dc5..2147fd688 100755\n> --- a/t/t4033-diff-patience.sh\n> +++ b/t/t4033-diff-patience.sh\n> @@ -13,6 +13,19 @@ test_expect_success '--ignore-space-at-eol with a single appended character' '\n>         grep \"^+.*X\" diff\n>  '\n>\n> +test_expect_success 'anchor' '\n> +       printf \"a\\nb\\nc\\n\" >pre &&\n> +       printf \"c\\na\\nb\\n\" >post &&\n> +\n> +       # without anchor, c is moved\n> +       test_expect_code 1 git diff --no-index --patience pre post >diff &&\n> +       grep \"^+c\" diff &&\n> +\n> +       # with anchor, a is moved\n> +       DIFF_ANCHOR=c test_expect_code 1 git diff --no-index --patience pre post >diff &&\n> +       grep \"^+a\" diff\n\nor rather: \"c is not moved, we don't care how the diff actually looks like\",\nso maybe\n      ! grep \"+c\" diff\n\n\n> diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\n> index a44e77632..195a60e57 100644\n> --- a/xdiff/xpatience.c\n> +++ b/xdiff/xpatience.c\n> @@ -62,6 +62,8 @@ struct hashmap {\n>                  * initially, \"next\" reflects only the order in file1.\n>                  */\n>                 struct entry *next, *previous;\n> +\n> +               unsigned anchor : 1;\n\nWhile this is RFC, I should not expect comments, though it would\nbe nice to have them in the final series. ;-)\n\n>         } *entries, *first, *last;\n>         /* were common records found? */\n>         unsigned long has_matches;\n> @@ -70,6 +72,14 @@ struct hashmap {\n>         xpparam_t const *xpp;\n>  };\n>\n> +static int is_anchor(const char *line)\n> +{\n> +       char *anchor = getenv(\"DIFF_ANCHOR\");\n> +       if (!anchor)\n> +               return 0;\n> +       return !strncmp(line, anchor, strlen(anchor));\n> +}\n> +\n>  /* The argument \"pass\" is 1 for the first file, 2 for the second. */\n>  static void insert_record(int line, struct hashmap *map, int pass)\n>  {\n> @@ -110,6 +120,7 @@ static void insert_record(int line, struct hashmap *map, int pass)\n>                 return;\n>         map->entries[index].line1 = line;\n>         map->entries[index].hash = record->ha;\n> +       map->entries[index].anchor = is_anchor(map->env->xdf1.recs[line - 1]->ptr);\n>         if (!map->first)\n>                 map->first = map->entries + index;\n>         if (map->last) {\n> @@ -192,14 +203,28 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)\n>         int longest = 0, i;\n>         struct entry *entry;\n>\n> +       /*\n> +        * If not -1, this entry in sequence must never be overridden. (Also,\n> +        * do not override entries in sequence before this entry, since it is\n> +        * useless.)\n> +        */\n> +       int anchor_i = -1;\n> +\n>         for (entry = map->first; entry; entry = entry->next) {\n>                 if (!entry->line2 || entry->line2 == NON_UNIQUE)\n>                         continue;\n>                 i = binary_search(sequence, longest, entry);\n>                 entry->previous = i < 0 ? NULL : sequence[i];\n> -               sequence[++i] = entry;\n> -               if (i == longest)\n> +               ++i;\n> +               if (i <= anchor_i)\n> +                       continue;\n> +               sequence[i] = entry;\n> +               if (anchor_i == -1 && entry->anchor) {\n> +                       anchor_i = i;\n> +                       longest = anchor_i + 1;\n> +               } else if (i == longest) {\n>                         longest++;\n> +               }\n>         }\n>\n>         /* No common unique lines were found */\n> --\n> 2.15.0.448.gf294e3d99a-goog\n>\n"},{"id":"333224","messageId":"xmqqwp2jvyhc.fsf@gitster.mtv.corp.google.com","threadId":"47286","inReplyTo":"20171121221717.155301-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] xdiff/xpatience: support anchoring a line","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-22T02:27:59Z","receivedAt":"2017-11-22T02:28:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> Teach the patience diff to support prohibiting a user-specified line\n> from appearing as a deletion or addition in the end result.\n>\n> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>\n> ---\n> I'm sending this out to see if a change similar to this would be\n> welcome. It is useful to me as a reviewer (to check my own code, e.g.\n> when checking [1]). Probably more design needs to go into this,\n> including the best way to specify the \"anchor\" line, and the correct\n> behavior when the anchor is either not found or appears more than once.\n>\n> Any thoughts?\n\nThis is a natural extension of the idea the patience algorithm is\nbuilt upon.  If this were a cumulative command line option that can\nbe given to specify multiple lines and can be used across the diff\nfamily, it would make a welcome addition, I would think.\n"},{"id":"333353","messageId":"20171122234152.72901-1-jonathantanmy@google.com","threadId":"47286","inReplyTo":"20171121221717.155301-1-jonathantanmy@google.com","subject":"[PATCH] xdiff/xpatience: support anchoring line(s)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-11-22T23:41:52Z","receivedAt":"2017-11-22T23:42:06Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Teach the patience diff to attempt preventing user-specified lines from\nappearing as a deletion or addition in the end result. The end user can\nuse this by specifying \"--anchor=<text>\" one or more times when using\nGit commands like \"diff\" and \"show\".\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\nActual patch instead of RFC.\n\nOne thing that might help is to warn if --anchor is used without\n--patience, but I couldn't find a good place to put that warning. Let me\nknow if you know of a good place.\n\nReplying to Stefan's and Junio's comments:\n\n> The solution you provide is a good thing to experiment with, but\n> longer term, I would want to have huge record of configs in which\n> humans selected the best diff, such that we can use that data\n> to reason about better automatic diff generation.\n> The diff heuristic was based on a lot of human generated data,\n> that was generated by Michael at the time. I wonder if we want to\n> permanently store the anchor so the data collection will happen\n> automatically over time.\n\nI think machine learning is beyond the scope of this patch :-)\n\n> or rather: \"c is not moved, we don't care how the diff actually looks\n> like\",\n> so maybe\n>       ! grep \"+c\" diff\n\nI think it's less error-prone to show \"a\" moving. With this, if the\ncommand somehow prints nothing, the test would still pass.\n\n> While this is RFC, I should not expect comments, though it would\n> be nice to have them in the final series. ;-)\n\nAdded comments :-)\n\n> This is a natural extension of the idea the patience algorithm is\n> built upon.  If this were a cumulative command line option that can\n> be given to specify multiple lines and can be used across the diff\n> family, it would make a welcome addition, I would think.\n\nSpecifying multiple lines - done.\n\nBy diff family, do you mean \"diff\", \"show\", and others? If yes, that has\nalso been done in this patch.\n---\n Documentation/diff-options.txt |  9 +++++++\n diff.c                         |  8 ++++++\n diff.h                         |  4 +++\n t/t4033-diff-patience.sh       | 59 ++++++++++++++++++++++++++++++++++++++++++\n xdiff/xdiff.h                  |  4 +++\n xdiff/xpatience.c              | 42 ++++++++++++++++++++++++++----\n 6 files changed, 121 insertions(+), 5 deletions(-)\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex dd0dba5b1..b17d62696 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -100,6 +100,15 @@ For instance, if you configured diff.algorithm variable to a\n non-default value and want to use the default one, then you\n have to use `--diff-algorithm=default` option.\n \n+--anchor=<text>::\n+\tThis option may be specified more than once.\n++\n+If the \"patience diff\" algorithm is used, Git attempts to prevent lines\n+starting with this text from appearing as a deletion or addition in the\n+output.\n++\n+If another diff algorithm is used, this has no effect.\n+\n --stat[=<width>[,<name-width>[,<count>]]]::\n \tGenerate a diffstat. By default, as much space as necessary\n \twill be used for the filename part, and the rest for the graph\ndiff --git a/diff.c b/diff.c\nindex 0763e8926..29a7176ee 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3210,6 +3210,8 @@ static void builtin_diff(const char *name_a,\n \t\tecbdata.opt = o;\n \t\tecbdata.header = header.len ? &header : NULL;\n \t\txpp.flags = o->xdl_opts;\n+\t\txpp.anchors = o->anchors;\n+\t\txpp.anchors_nr = o->anchors_nr;\n \t\txecfg.ctxlen = o->context;\n \t\txecfg.interhunkctxlen = o->interhunkcontext;\n \t\txecfg.flags = XDL_EMIT_FUNCNAMES;\n@@ -3302,6 +3304,8 @@ static void builtin_diffstat(const char *name_a, const char *name_b,\n \t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\txpp.flags = o->xdl_opts;\n+\t\txpp.anchors = o->anchors;\n+\t\txpp.anchors_nr = o->anchors_nr;\n \t\txecfg.ctxlen = o->context;\n \t\txecfg.interhunkctxlen = o->interhunkcontext;\n \t\tif (xdi_diff_outf(&mf1, &mf2, diffstat_consume, diffstat,\n@@ -4608,6 +4612,10 @@ int diff_opt_parse(struct diff_options *options,\n \t\toptions->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;\n \t\toptions->xdl_opts |= value;\n \t\treturn argcount;\n+\t} else if (skip_prefix(arg, \"--anchor=\", &arg)) {\n+\t\tALLOC_GROW(options->anchors, options->anchors_nr + 1,\n+\t\t\t   options->anchors_alloc);\n+\t\toptions->anchors[options->anchors_nr++] = xstrdup(arg);\n \t}\n \n \t/* flags options */\ndiff --git a/diff.h b/diff.h\nindex 0fb18dd73..7cf276f07 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -166,6 +166,10 @@ struct diff_options {\n \tconst char *stat_sep;\n \tlong xdl_opts;\n \n+\t/* see Documentation/diff-options.txt */\n+\tchar **anchors;\n+\tsize_t anchors_nr, anchors_alloc;\n+\n \tint stat_width;\n \tint stat_name_width;\n \tint stat_graph_width;\ndiff --git a/t/t4033-diff-patience.sh b/t/t4033-diff-patience.sh\nindex 113304dc5..2d00d1056 100755\n--- a/t/t4033-diff-patience.sh\n+++ b/t/t4033-diff-patience.sh\n@@ -13,6 +13,65 @@ test_expect_success '--ignore-space-at-eol with a single appended character' '\n \tgrep \"^+.*X\" diff\n '\n \n+test_expect_success '--anchor' '\n+\tprintf \"a\\nb\\nc\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\n\" >post &&\n+\n+\t# without anchor, c is moved\n+\ttest_expect_code 1 git diff --no-index --patience pre post >diff &&\n+\tgrep \"^+c\" diff &&\n+\n+\t# with anchor, a is moved\n+\ttest_expect_code 1 git diff --no-index --patience --anchor=c pre post >diff &&\n+\tgrep \"^+a\" diff\n+'\n+\n+test_expect_success '--anchor multiple' '\n+\tprintf \"a\\nb\\nc\\nd\\ne\\nf\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\nf\\nd\\ne\\n\" >post &&\n+\n+\t# with 1 anchor, c is not moved, but f is moved\n+\ttest_expect_code 1 git diff --no-index --patience --anchor=c pre post >diff &&\n+\tgrep \"^+a\" diff && # a is moved instead of c\n+\tgrep \"^+f\" diff &&\n+\n+\t# with 2 anchors, c and f are not moved\n+\ttest_expect_code 1 git diff --no-index --patience --anchor=c --anchor=f pre post >diff &&\n+\tgrep \"^+a\" diff &&\n+\tgrep \"^+d\" diff # d is moved instead of f\n+'\n+\n+test_expect_success '--anchor with nonexistent line has no effect' '\n+\tprintf \"a\\nb\\nc\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\n\" >post &&\n+\n+\ttest_expect_code 1 git diff --no-index --patience --anchor=x pre post >diff &&\n+\tgrep \"^+c\" diff\n+'\n+\n+test_expect_success 'diff still produced with impossible multiple --anchor' '\n+\tprintf \"a\\nb\\nc\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\n\" >post &&\n+\n+\ttest_expect_code 1 git diff --no-index --patience --anchor=a --anchor=c pre post >diff &&\n+\tmv post expected_post &&\n+\tgit apply diff &&\n+\tdiff expected_post post # make sure that the diff is correct\n+'\n+\n+test_expect_success '--anchor works with other commands like \"git show\"' '\n+\tprintf \"a\\nb\\nc\\n\" >file &&\n+\tgit add file &&\n+\tgit commit -m foo &&\n+\tprintf \"c\\na\\nb\\n\" >file &&\n+\tgit add file &&\n+\tgit commit -m foo &&\n+\n+\t# with anchor, a is moved\n+\tgit show --patience --anchor=c >diff &&\n+\tgrep \"^+a\" diff\n+'\n+\n test_diff_frobnitz \"patience\"\n \n test_diff_unique \"patience\"\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 785ecb089..e6217e1d7 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -80,6 +80,10 @@ typedef struct s_mmbuffer {\n \n typedef struct s_xpparam {\n \tunsigned long flags;\n+\n+\t/* See Documentation/diff-options.txt. */\n+\tchar **anchors;\n+\tsize_t anchors_nr;\n } xpparam_t;\n \n typedef struct s_xdemitcb {\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex a44e77632..f55c9fb11 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -62,6 +62,12 @@ struct hashmap {\n \t\t * initially, \"next\" reflects only the order in file1.\n \t\t */\n \t\tstruct entry *next, *previous;\n+\n+\t\t/*\n+\t\t * If 1, this entry can serve as the anchor. See\n+\t\t * Documentation/diff-options.txt for more information.\n+\t\t */\n+\t\tunsigned anchor : 1;\n \t} *entries, *first, *last;\n \t/* were common records found? */\n \tunsigned long has_matches;\n@@ -70,8 +76,19 @@ struct hashmap {\n \txpparam_t const *xpp;\n };\n \n+static int is_anchor(xpparam_t const *xpp, const char *line)\n+{\n+\tint i;\n+\tfor (i = 0; i < xpp->anchors_nr; i++) {\n+\t\tif (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i])))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n /* The argument \"pass\" is 1 for the first file, 2 for the second. */\n-static void insert_record(int line, struct hashmap *map, int pass)\n+static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n+\t\t\t  int pass)\n {\n \txrecord_t **records = pass == 1 ?\n \t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n@@ -110,6 +127,7 @@ static void insert_record(int line, struct hashmap *map, int pass)\n \t\treturn;\n \tmap->entries[index].line1 = line;\n \tmap->entries[index].hash = record->ha;\n+\tmap->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr);\n \tif (!map->first)\n \t\tmap->first = map->entries + index;\n \tif (map->last) {\n@@ -147,11 +165,11 @@ static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,\n \n \t/* First, fill with entries from the first file */\n \twhile (count1--)\n-\t\tinsert_record(line1++, result, 1);\n+\t\tinsert_record(xpp, line1++, result, 1);\n \n \t/* Then search for matches in the second file */\n \twhile (count2--)\n-\t\tinsert_record(line2++, result, 2);\n+\t\tinsert_record(xpp, line2++, result, 2);\n \n \treturn 0;\n }\n@@ -192,14 +210,28 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)\n \tint longest = 0, i;\n \tstruct entry *entry;\n \n+\t/*\n+\t * If not -1, this entry in sequence must never be overridden.\n+\t * Therefore, overriding entries before this has no effect, so\n+\t * do not do that either.\n+\t */\n+\tint anchor_i = -1;\n+\n \tfor (entry = map->first; entry; entry = entry->next) {\n \t\tif (!entry->line2 || entry->line2 == NON_UNIQUE)\n \t\t\tcontinue;\n \t\ti = binary_search(sequence, longest, entry);\n \t\tentry->previous = i < 0 ? NULL : sequence[i];\n-\t\tsequence[++i] = entry;\n-\t\tif (i == longest)\n+\t\t++i;\n+\t\tif (i <= anchor_i)\n+\t\t\tcontinue;\n+\t\tsequence[i] = entry;\n+\t\tif (entry->anchor) {\n+\t\t\tanchor_i = i;\n+\t\t\tlongest = anchor_i + 1;\n+\t\t} else if (i == longest) {\n \t\t\tlongest++;\n+\t\t}\n \t}\n \n \t/* No common unique lines were found */\n-- \n2.15.0.448.gf294e3d99a-goog\n\n"},{"id":"333361","messageId":"CAGZ79kYOovfAGNseAevsZOP2emxFCZfJpH=EJD5L0_vVnMZ-2Q@mail.gmail.com","threadId":"47286","inReplyTo":"20171122234152.72901-1-jonathantanmy@google.com","subject":"Re: [PATCH] xdiff/xpatience: support anchoring line(s)","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-11-23T00:15:50Z","receivedAt":"2017-11-23T00:15:56Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Nov 22, 2017 at 3:41 PM, Jonathan Tan <jonathantanmy@google.com> wrote:\n> Teach the patience diff to attempt preventing user-specified lines from\n> appearing as a deletion or addition in the end result. The end user can\n> use this by specifying \"--anchor=<text>\" one or more times when using\n> Git commands like \"diff\" and \"show\".\n>\n> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>\n> ---\n> Actual patch instead of RFC.\n>\n> One thing that might help is to warn if --anchor is used without\n> --patience, but I couldn't find a good place to put that warning. Let me\n> know if you know of a good place.\n\nWould it make sense to have `--anchor` imply patience?\n(not necessarily in this patch, might be a \"yes, let's do\nit in a year when users complain\")\n\n> Replying to Stefan's and Junio's comments:\n>\n>> The solution you provide is a good thing to experiment with, but\n>> longer term, I would want to have huge record of configs in which\n>> humans selected the best diff, such that we can use that data\n>> to reason about better automatic diff generation.\n>> The diff heuristic was based on a lot of human generated data,\n>> that was generated by Michael at the time. I wonder if we want to\n>> permanently store the anchor so the data collection will happen\n>> automatically over time.\n>\n> I think machine learning is beyond the scope of this patch :-)\n\nagreed; I just wanted to share what I think we could do in the future\nto select sane default. For that we'd want to collect some \"most useful\"\nconfigurations.\n\nWhen I proposed separate flags for the move detection regarding\nignoring whitespaces, the question \"how is the user sanely select\nfrom so many flags?\" came up. And in that spirit I would want think\nadding this rather fundamental flag, and then machine learn (e.g. the\nweights in traversing the diff matrix) off of this collected data later\nmight be a viable approach.\n\n>> or rather: \"c is not moved, we don't care how the diff actually looks\n>> like\",\n>> so maybe\n>>       ! grep \"+c\" diff\n>\n> I think it's less error-prone to show \"a\" moving. With this, if the\n> command somehow prints nothing, the test would still pass.\n\nMakes sense.\n\n> diff --git a/t/t4033-diff-patience.sh b/t/t4033-diff-patience.sh\n> index 113304dc5..2d00d1056 100755\n> --- a/t/t4033-diff-patience.sh\n> +++ b/t/t4033-diff-patience.sh\n\nI was waiting for\n\n    test_expect_success 'one --anchor anchors many lines' '\n        printf \"a\\nb\\na\\nc\\na\\n\" >file && # many 'a's\n        ....\n        --anchor=a\n        ...\n\n\nThanks for writing this patch,\nI hope we can make use of this addition eventually a lot. :)\n\nStefan\n"},{"id":"333364","messageId":"xmqqa7zdsqb6.fsf@gitster.mtv.corp.google.com","threadId":"47286","inReplyTo":"20171122234152.72901-1-jonathantanmy@google.com","subject":"Re: [PATCH] xdiff/xpatience: support anchoring line(s)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-23T02:05:01Z","receivedAt":"2017-11-23T02:05:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> One thing that might help is to warn if --anchor is used without\n> --patience, but I couldn't find a good place to put that warning. Let me\n> know if you know of a good place.\n\nHow about dropping --anchor option and do it as \"--patience=<pattern>\"?\n"},{"id":"333365","messageId":"xmqq3755sprp.fsf@gitster.mtv.corp.google.com","threadId":"47286","inReplyTo":"xmqqa7zdsqb6.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] xdiff/xpatience: support anchoring line(s)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-23T02:16:42Z","receivedAt":"2017-11-23T02:16:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Jonathan Tan <jonathantanmy@google.com> writes:\n>\n>> One thing that might help is to warn if --anchor is used without\n>> --patience, but I couldn't find a good place to put that warning. Let me\n>> know if you know of a good place.\n>\n> How about dropping --anchor option and do it as \"--patience=<pattern>\"?\n\nWell, that may not be an optimal suggestion, as it is always a pain\nto have to deal with an option with optional argument.\n\nI understand that the case you would really want to warn against is\n\n    git diff --histogram --anchor=foo\n\nand not\n\n    git diff --anchor=foo\n\nas it is sensible to turn --patience on implicitly.  Perhaps a good\nstarting point might be to rename the option to include \"patience\"\nsomewhere in its name (\"--patience-anchor=<pattern>\"?) to make it\nmore obvious that it is about helping the patience algorithm.  And\nthen make \"--patience-anchor=<pattern>\" without any other algorithm\nselection option to behave as if \"--patience\" was also given.\n\nWhat do we do when\n\n    git diff --histogram --patience\n\nis given?  Do we warn?  If we don't, perhaps it may not be too bad\nif \n\n    git diff --histogram --patience-anchor=foo\n    git diff --patience-anchor=foo --histogram\n\ndid not get any warning.  Instead we just implicitly turn any\noccurence of --patience-anchor=foo into --patience followed by the\nsame option, and assume that the user wanted the usual \"last one\nwins\" semantics.  It would turn patience on for the former, and\nignore the anchor for the latter and use historgram.\n\n"},{"id":"333370","messageId":"xmqqh8tlr9sp.fsf@gitster.mtv.corp.google.com","threadId":"47286","inReplyTo":"xmqq3755sprp.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] xdiff/xpatience: support anchoring line(s)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-23T02:47:02Z","receivedAt":"2017-11-23T02:47:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> What do we do when\n>\n>     git diff --histogram --patience\n>\n> is given?  Do we warn?  If we don't, perhaps it may not be too bad\n> if \n>\n>     git diff --histogram --patience-anchor=foo\n>     git diff --patience-anchor=foo --histogram\n>\n> did not get any warning.  Instead we just implicitly turn any\n> occurence of --patience-anchor=foo into --patience followed by the\n> same option, and assume that the user wanted the usual \"last one\n> wins\" semantics.  It would turn patience on for the former, and\n> ignore the anchor for the latter and use historgram.\n\nThinking about this a bit more, I do like the basic idea of the UI\neven better.  What we could do is to sell this to the end users as a\nnew kind of diff algorithm choice (i.e. myers, patience, ... will\ngain a new friend) that internally happens to be implemented by\npiggybacking on patience (just like minimal is piggybacking on\nmyers) and call it \"anchor\".  Then just like this command line\n\n    git diff --histogram --patience\n\nmakes the last one win without complaint, it is sane that these\ncommand lines\n\n    git diff --histogram --anchored=<pattern>\n    git diff --anchored=<pattern> --histogram\n\nmake the last one win without complaint, either.\n\nHmm?\n\n"},{"id":"333624","messageId":"20171127103055.a10ccec6b4e2adc2c2c26c22@google.com","threadId":"47286","inReplyTo":"xmqqh8tlr9sp.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] xdiff/xpatience: support anchoring line(s)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-11-27T18:30:55Z","receivedAt":"2017-11-27T18:31:03Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Thu, 23 Nov 2017 11:47:02 +0900\nJunio C Hamano <gitster@pobox.com> wrote:\n\n> Thinking about this a bit more, I do like the basic idea of the UI\n> even better.  What we could do is to sell this to the end users as a\n> new kind of diff algorithm choice (i.e. myers, patience, ... will\n> gain a new friend) that internally happens to be implemented by\n> piggybacking on patience (just like minimal is piggybacking on\n> myers) and call it \"anchor\".  Then just like this command line\n> \n>     git diff --histogram --patience\n> \n> makes the last one win without complaint, it is sane that these\n> command lines\n> \n>     git diff --histogram --anchored=<pattern>\n>     git diff --anchored=<pattern> --histogram\n> \n> make the last one win without complaint, either.\n> \n> Hmm?\n\nThis sounds good. There will be a bit of inconsistency in that in \"git\ndiff --anchored=<pattern1> --anchored=<pattern2>\", it is not the last\none that wins, but both of them will in fact be used. But I think that\nin practice, this will be fine.\n\nI'll send out another version with this UI (and with Stefan's test\nsuggestion).\n"},{"id":"333628","messageId":"20171127194747.118254-1-jonathantanmy@google.com","threadId":"47286","inReplyTo":"20171122234152.72901-1-jonathantanmy@google.com","subject":"[PATCH v2] diff: support anchoring line(s)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-11-27T19:47:47Z","receivedAt":"2017-11-27T19:47:56Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Teach diff a new algorithm, one that attempts to prevent user-specified\nlines from appearing as a deletion or addition in the end result. The\nend user can use this by specifying \"--anchored=<text>\" one or more\ntimes when using Git commands like \"diff\" and \"show\".\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\nIn v2, the UI treats it as a new algorithm. (Internally it's still an\noption for \"patience\".)\n\nStefan suggested that I add a test where a single --anchored=<> matches\nmultiple lines, and that reminded me that the patience algorithm only\nreally works on unique lines. I have updated the documentation to remark\non that, and also added a test to show what happens. I have also added a\ntest to show that later algorithm options override earlier ones.\n---\n Documentation/diff-options.txt | 10 +++++\n diff.c                         | 22 +++++++++-\n diff.h                         |  4 ++\n t/t4064-diff-anchored.sh       | 94 ++++++++++++++++++++++++++++++++++++++++++\n xdiff/xdiff.h                  |  4 ++\n xdiff/xpatience.c              | 42 ++++++++++++++++---\n 6 files changed, 169 insertions(+), 7 deletions(-)\n create mode 100755 t/t4064-diff-anchored.sh\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex dd0dba5b1..6ce39fb69 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -80,6 +80,16 @@ endif::git-format-patch[]\n --histogram::\n \tGenerate a diff using the \"histogram diff\" algorithm.\n \n+--anchored=<text>::\n+\tGenerate a diff using the \"anchored diff\" algorithm.\n++\n+This option may be specified more than once.\n++\n+If a line exists in both the source and destination, exists only once,\n+and starts with this text, this algorithm attempts to prevent it from\n+appearing as a deletion or addition in the output. It uses the \"patience\n+diff\" algorithm internally.\n+\n --diff-algorithm={patience|minimal|histogram|myers}::\n \tChoose a diff algorithm. The variants are as follows:\n +\ndiff --git a/diff.c b/diff.c\nindex 0763e8926..98aa638f8 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3210,6 +3210,8 @@ static void builtin_diff(const char *name_a,\n \t\tecbdata.opt = o;\n \t\tecbdata.header = header.len ? &header : NULL;\n \t\txpp.flags = o->xdl_opts;\n+\t\txpp.anchors = o->anchors;\n+\t\txpp.anchors_nr = o->anchors_nr;\n \t\txecfg.ctxlen = o->context;\n \t\txecfg.interhunkctxlen = o->interhunkcontext;\n \t\txecfg.flags = XDL_EMIT_FUNCNAMES;\n@@ -3302,6 +3304,8 @@ static void builtin_diffstat(const char *name_a, const char *name_b,\n \t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\txpp.flags = o->xdl_opts;\n+\t\txpp.anchors = o->anchors;\n+\t\txpp.anchors_nr = o->anchors_nr;\n \t\txecfg.ctxlen = o->context;\n \t\txecfg.interhunkctxlen = o->interhunkcontext;\n \t\tif (xdi_diff_outf(&mf1, &mf2, diffstat_consume, diffstat,\n@@ -4594,9 +4598,18 @@ int diff_opt_parse(struct diff_options *options,\n \t\tDIFF_XDL_SET(options, INDENT_HEURISTIC);\n \telse if (!strcmp(arg, \"--no-indent-heuristic\"))\n \t\tDIFF_XDL_CLR(options, INDENT_HEURISTIC);\n-\telse if (!strcmp(arg, \"--patience\"))\n+\telse if (!strcmp(arg, \"--patience\")) {\n+\t\tint i;\n \t\toptions->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);\n-\telse if (!strcmp(arg, \"--histogram\"))\n+\t\t/*\n+\t\t * Both --patience and --anchored use PATIENCE_DIFF\n+\t\t * internally, so remove any anchors previously\n+\t\t * specified.\n+\t\t */\n+\t\tfor (i = 0; i < options->anchors_nr; i++)\n+\t\t\tfree(options->anchors[i]);\n+\t\toptions->anchors_nr = 0;\n+\t} else if (!strcmp(arg, \"--histogram\"))\n \t\toptions->xdl_opts = DIFF_WITH_ALG(options, HISTOGRAM_DIFF);\n \telse if ((argcount = parse_long_opt(\"diff-algorithm\", av, &optarg))) {\n \t\tlong value = parse_algorithm_value(optarg);\n@@ -4608,6 +4621,11 @@ int diff_opt_parse(struct diff_options *options,\n \t\toptions->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;\n \t\toptions->xdl_opts |= value;\n \t\treturn argcount;\n+\t} else if (skip_prefix(arg, \"--anchored=\", &arg)) {\n+\t\toptions->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);\n+\t\tALLOC_GROW(options->anchors, options->anchors_nr + 1,\n+\t\t\t   options->anchors_alloc);\n+\t\toptions->anchors[options->anchors_nr++] = xstrdup(arg);\n \t}\n \n \t/* flags options */\ndiff --git a/diff.h b/diff.h\nindex 0fb18dd73..7cf276f07 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -166,6 +166,10 @@ struct diff_options {\n \tconst char *stat_sep;\n \tlong xdl_opts;\n \n+\t/* see Documentation/diff-options.txt */\n+\tchar **anchors;\n+\tsize_t anchors_nr, anchors_alloc;\n+\n \tint stat_width;\n \tint stat_name_width;\n \tint stat_graph_width;\ndiff --git a/t/t4064-diff-anchored.sh b/t/t4064-diff-anchored.sh\nnew file mode 100755\nindex 000000000..b3f510f04\n--- /dev/null\n+++ b/t/t4064-diff-anchored.sh\n@@ -0,0 +1,94 @@\n+#!/bin/sh\n+\n+test_description='anchored diff algorithm'\n+\n+. ./test-lib.sh\n+\n+test_expect_success '--anchored' '\n+\tprintf \"a\\nb\\nc\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\n\" >post &&\n+\n+\t# normally, c is moved to produce the smallest diff\n+\ttest_expect_code 1 git diff --no-index pre post >diff &&\n+\tgrep \"^+c\" diff &&\n+\n+\t# with anchor, a is moved\n+\ttest_expect_code 1 git diff --no-index --anchored=c pre post >diff &&\n+\tgrep \"^+a\" diff\n+'\n+\n+test_expect_success '--anchored multiple' '\n+\tprintf \"a\\nb\\nc\\nd\\ne\\nf\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\nf\\nd\\ne\\n\" >post &&\n+\n+\t# with 1 anchor, c is not moved, but f is moved\n+\ttest_expect_code 1 git diff --no-index --anchored=c pre post >diff &&\n+\tgrep \"^+a\" diff && # a is moved instead of c\n+\tgrep \"^+f\" diff &&\n+\n+\t# with 2 anchors, c and f are not moved\n+\ttest_expect_code 1 git diff --no-index --anchored=c --anchored=f pre post >diff &&\n+\tgrep \"^+a\" diff &&\n+\tgrep \"^+d\" diff # d is moved instead of f\n+'\n+\n+test_expect_success '--anchored with nonexistent line has no effect' '\n+\tprintf \"a\\nb\\nc\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\n\" >post &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=x pre post >diff &&\n+\tgrep \"^+c\" diff\n+'\n+\n+test_expect_success '--anchored with non-unique line has no effect' '\n+\tprintf \"a\\nb\\nc\\nd\\ne\\nc\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\nc\\nd\\ne\\n\" >post &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=c pre post >diff &&\n+\tgrep \"^+c\" diff\n+'\n+\n+test_expect_success 'diff still produced with impossible multiple --anchored' '\n+\tprintf \"a\\nb\\nc\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\n\" >post &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=a --anchored=c pre post >diff &&\n+\tmv post expected_post &&\n+\n+\t# Ensure that the diff is correct by applying it and then\n+\t# comparing the result with the original\n+\tgit apply diff &&\n+\tdiff expected_post post\n+'\n+\n+test_expect_success 'later algorithm arguments override earlier ones' '\n+\tprintf \"a\\nb\\nc\\n\" >pre &&\n+\tprintf \"c\\na\\nb\\n\" >post &&\n+\n+\ttest_expect_code 1 git diff --no-index --patience --anchored=c pre post >diff &&\n+\tgrep \"^+a\" diff &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=c --patience pre post >diff &&\n+\tgrep \"^+c\" diff &&\n+\n+\ttest_expect_code 1 git diff --no-index --histogram --anchored=c pre post >diff &&\n+\tgrep \"^+a\" diff &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=c --histogram pre post >diff &&\n+\tgrep \"^+c\" diff\n+'\n+\n+test_expect_success '--anchored works with other commands like \"git show\"' '\n+\tprintf \"a\\nb\\nc\\n\" >file &&\n+\tgit add file &&\n+\tgit commit -m foo &&\n+\tprintf \"c\\na\\nb\\n\" >file &&\n+\tgit add file &&\n+\tgit commit -m foo &&\n+\n+\t# with anchor, a is moved\n+\tgit show --patience --anchored=c >diff &&\n+\tgrep \"^+a\" diff\n+'\n+\n+test_done\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 785ecb089..e6217e1d7 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -80,6 +80,10 @@ typedef struct s_mmbuffer {\n \n typedef struct s_xpparam {\n \tunsigned long flags;\n+\n+\t/* See Documentation/diff-options.txt. */\n+\tchar **anchors;\n+\tsize_t anchors_nr;\n } xpparam_t;\n \n typedef struct s_xdemitcb {\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex a44e77632..f3573d9f0 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -62,6 +62,12 @@ struct hashmap {\n \t\t * initially, \"next\" reflects only the order in file1.\n \t\t */\n \t\tstruct entry *next, *previous;\n+\n+\t\t/*\n+\t\t * If 1, this entry can serve as an anchor. See\n+\t\t * Documentation/diff-options.txt for more information.\n+\t\t */\n+\t\tunsigned anchor : 1;\n \t} *entries, *first, *last;\n \t/* were common records found? */\n \tunsigned long has_matches;\n@@ -70,8 +76,19 @@ struct hashmap {\n \txpparam_t const *xpp;\n };\n \n+static int is_anchor(xpparam_t const *xpp, const char *line)\n+{\n+\tint i;\n+\tfor (i = 0; i < xpp->anchors_nr; i++) {\n+\t\tif (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i])))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n /* The argument \"pass\" is 1 for the first file, 2 for the second. */\n-static void insert_record(int line, struct hashmap *map, int pass)\n+static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n+\t\t\t  int pass)\n {\n \txrecord_t **records = pass == 1 ?\n \t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n@@ -110,6 +127,7 @@ static void insert_record(int line, struct hashmap *map, int pass)\n \t\treturn;\n \tmap->entries[index].line1 = line;\n \tmap->entries[index].hash = record->ha;\n+\tmap->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr);\n \tif (!map->first)\n \t\tmap->first = map->entries + index;\n \tif (map->last) {\n@@ -147,11 +165,11 @@ static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,\n \n \t/* First, fill with entries from the first file */\n \twhile (count1--)\n-\t\tinsert_record(line1++, result, 1);\n+\t\tinsert_record(xpp, line1++, result, 1);\n \n \t/* Then search for matches in the second file */\n \twhile (count2--)\n-\t\tinsert_record(line2++, result, 2);\n+\t\tinsert_record(xpp, line2++, result, 2);\n \n \treturn 0;\n }\n@@ -192,14 +210,28 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)\n \tint longest = 0, i;\n \tstruct entry *entry;\n \n+\t/*\n+\t * If not -1, this entry in sequence must never be overridden.\n+\t * Therefore, overriding entries before this has no effect, so\n+\t * do not do that either.\n+\t */\n+\tint anchor_i = -1;\n+\n \tfor (entry = map->first; entry; entry = entry->next) {\n \t\tif (!entry->line2 || entry->line2 == NON_UNIQUE)\n \t\t\tcontinue;\n \t\ti = binary_search(sequence, longest, entry);\n \t\tentry->previous = i < 0 ? NULL : sequence[i];\n-\t\tsequence[++i] = entry;\n-\t\tif (i == longest)\n+\t\t++i;\n+\t\tif (i <= anchor_i)\n+\t\t\tcontinue;\n+\t\tsequence[i] = entry;\n+\t\tif (entry->anchor) {\n+\t\t\tanchor_i = i;\n+\t\t\tlongest = anchor_i + 1;\n+\t\t} else if (i == longest) {\n \t\t\tlongest++;\n+\t\t}\n \t}\n \n \t/* No common unique lines were found */\n-- \n2.15.0.417.g466bffb3ac-goog\n\n"},{"id":"333665","messageId":"xmqq1skj9o7r.fsf@gitster.mtv.corp.google.com","threadId":"47286","inReplyTo":"20171127194747.118254-1-jonathantanmy@google.com","subject":"Re: [PATCH v2] diff: support anchoring line(s)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-28T01:38:48Z","receivedAt":"2017-11-28T01:38:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> -\telse if (!strcmp(arg, \"--patience\"))\n> +\telse if (!strcmp(arg, \"--patience\")) {\n> +\t\tint i;\n>  \t\toptions->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);\n> -\telse if (!strcmp(arg, \"--histogram\"))\n> +\t\t/*\n> +\t\t * Both --patience and --anchored use PATIENCE_DIFF\n> +\t\t * internally, so remove any anchors previously\n> +\t\t * specified.\n> +\t\t */\n> +\t\tfor (i = 0; i < options->anchors_nr; i++)\n> +\t\t\tfree(options->anchors[i]);\n> +\t\toptions->anchors_nr = 0;\n\nThis makes sense, but \"--diff-algorithm=patience\" would want to do\nthe same, I suspect, so the loop would want to become a little\nhelper function \"clear_patience_anchors(options)\" or something like\nthat.\n\n> diff --git a/t/t4064-diff-anchored.sh b/t/t4064-diff-anchored.sh\n> new file mode 100755\n> index 000000000..b3f510f04\n> --- /dev/null\n> +++ b/t/t4064-diff-anchored.sh\n> @@ -0,0 +1,94 @@\n> +#!/bin/sh\n> +\n> +test_description='anchored diff algorithm'\n> +\n> +. ./test-lib.sh\n> +\n> +test_expect_success '--anchored' '\n> +\tprintf \"a\\nb\\nc\\n\" >pre &&\n> +\tprintf \"c\\na\\nb\\n\" >post &&\n\nThis may be too little to matter, but I'd find\n\n\tprintf \"%s\\n\" a b c >pre\n\nvastly easier to read.  Or perhaps just use\n\n\ttest_write_lines a b c >pre\n\n"},{"id":"333702","messageId":"20171128184703.155931-1-jonathantanmy@google.com","threadId":"47286","inReplyTo":"xmqq1skj9o7r.fsf@gitster.mtv.corp.google.com","subject":"[PATCH v3] diff: support anchoring line(s)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-11-28T18:47:03Z","receivedAt":"2017-11-28T18:47:18Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Teach diff a new algorithm, one that attempts to prevent user-specified\nlines from appearing as a deletion or addition in the end result. The\nend user can use this by specifying \"--anchored=<text>\" one or more\ntimes when using Git commands like \"diff\" and \"show\".\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\nv3 addresses Junio's comments.\n\n> This makes sense, but \"--diff-algorithm=patience\" would want to do\n> the same, I suspect, so the loop would want to become a little\n> helper function \"clear_patience_anchors(options)\" or something like\n> that.\n\nDone. Also updated a test to test the interaction of\n\"--diff-algorithm=patience\" with \"--anchored=<>\".\n\n> This may be too little to matter, but I'd find\n>\n> \tprintf \"%s\\n\" a b c >pre\n>\n> vastly easier to read.  Or perhaps just use\n>\n> \ttest_write_lines a b c >pre\n\nThanks for the pointer to test_write_lines - I used that and it is\nindeed clearer.\n---\n Documentation/diff-options.txt |  10 +++++\n diff.c                         |  31 ++++++++++++-\n diff.h                         |   4 ++\n t/t4064-diff-anchored.sh       | 100 +++++++++++++++++++++++++++++++++++++++++\n xdiff/xdiff.h                  |   4 ++\n xdiff/xpatience.c              |  42 ++++++++++++++---\n 6 files changed, 184 insertions(+), 7 deletions(-)\n create mode 100755 t/t4064-diff-anchored.sh\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex dd0dba5b1..6ce39fb69 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -80,6 +80,16 @@ endif::git-format-patch[]\n --histogram::\n \tGenerate a diff using the \"histogram diff\" algorithm.\n \n+--anchored=<text>::\n+\tGenerate a diff using the \"anchored diff\" algorithm.\n++\n+This option may be specified more than once.\n++\n+If a line exists in both the source and destination, exists only once,\n+and starts with this text, this algorithm attempts to prevent it from\n+appearing as a deletion or addition in the output. It uses the \"patience\n+diff\" algorithm internally.\n+\n --diff-algorithm={patience|minimal|histogram|myers}::\n \tChoose a diff algorithm. The variants are as follows:\n +\ndiff --git a/diff.c b/diff.c\nindex 0763e8926..7149ff627 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3210,6 +3210,8 @@ static void builtin_diff(const char *name_a,\n \t\tecbdata.opt = o;\n \t\tecbdata.header = header.len ? &header : NULL;\n \t\txpp.flags = o->xdl_opts;\n+\t\txpp.anchors = o->anchors;\n+\t\txpp.anchors_nr = o->anchors_nr;\n \t\txecfg.ctxlen = o->context;\n \t\txecfg.interhunkctxlen = o->interhunkcontext;\n \t\txecfg.flags = XDL_EMIT_FUNCNAMES;\n@@ -3302,6 +3304,8 @@ static void builtin_diffstat(const char *name_a, const char *name_b,\n \t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\txpp.flags = o->xdl_opts;\n+\t\txpp.anchors = o->anchors;\n+\t\txpp.anchors_nr = o->anchors_nr;\n \t\txecfg.ctxlen = o->context;\n \t\txecfg.interhunkctxlen = o->interhunkcontext;\n \t\tif (xdi_diff_outf(&mf1, &mf2, diffstat_consume, diffstat,\n@@ -4487,6 +4491,21 @@ static int parse_ws_error_highlight_opt(struct diff_options *opt, const char *ar\n \treturn 1;\n }\n \n+/*\n+ * Clear the anchors configured for the PATIENCE_DIFF algorithm.\n+ *\n+ * This must be called whenever a command-line argument indicating that\n+ * the patience algorithm is to be used is seen, because the patience\n+ * and anchored algorithms both use PATIENCE_DIFF internally.\n+ */\n+static void clear_patience_anchors(struct diff_options *options)\n+{\n+\tint i;\n+\tfor (i = 0; i < options->anchors_nr; i++)\n+\t\tfree(options->anchors[i]);\n+\toptions->anchors_nr = 0;\n+}\n+\n int diff_opt_parse(struct diff_options *options,\n \t\t   const char **av, int ac, const char *prefix)\n {\n@@ -4594,9 +4613,10 @@ int diff_opt_parse(struct diff_options *options,\n \t\tDIFF_XDL_SET(options, INDENT_HEURISTIC);\n \telse if (!strcmp(arg, \"--no-indent-heuristic\"))\n \t\tDIFF_XDL_CLR(options, INDENT_HEURISTIC);\n-\telse if (!strcmp(arg, \"--patience\"))\n+\telse if (!strcmp(arg, \"--patience\")) {\n \t\toptions->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);\n-\telse if (!strcmp(arg, \"--histogram\"))\n+\t\tclear_patience_anchors(options);\n+\t} else if (!strcmp(arg, \"--histogram\"))\n \t\toptions->xdl_opts = DIFF_WITH_ALG(options, HISTOGRAM_DIFF);\n \telse if ((argcount = parse_long_opt(\"diff-algorithm\", av, &optarg))) {\n \t\tlong value = parse_algorithm_value(optarg);\n@@ -4607,7 +4627,14 @@ int diff_opt_parse(struct diff_options *options,\n \t\tDIFF_XDL_CLR(options, NEED_MINIMAL);\n \t\toptions->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;\n \t\toptions->xdl_opts |= value;\n+\t\tif (value == XDF_PATIENCE_DIFF)\n+\t\t\tclear_patience_anchors(options);\n \t\treturn argcount;\n+\t} else if (skip_prefix(arg, \"--anchored=\", &arg)) {\n+\t\toptions->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);\n+\t\tALLOC_GROW(options->anchors, options->anchors_nr + 1,\n+\t\t\t   options->anchors_alloc);\n+\t\toptions->anchors[options->anchors_nr++] = xstrdup(arg);\n \t}\n \n \t/* flags options */\ndiff --git a/diff.h b/diff.h\nindex 0fb18dd73..7cf276f07 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -166,6 +166,10 @@ struct diff_options {\n \tconst char *stat_sep;\n \tlong xdl_opts;\n \n+\t/* see Documentation/diff-options.txt */\n+\tchar **anchors;\n+\tsize_t anchors_nr, anchors_alloc;\n+\n \tint stat_width;\n \tint stat_name_width;\n \tint stat_graph_width;\ndiff --git a/t/t4064-diff-anchored.sh b/t/t4064-diff-anchored.sh\nnew file mode 100755\nindex 000000000..d51ca2c35\n--- /dev/null\n+++ b/t/t4064-diff-anchored.sh\n@@ -0,0 +1,100 @@\n+#!/bin/sh\n+\n+test_description='anchored diff algorithm'\n+\n+. ./test-lib.sh\n+\n+test_expect_success '--anchored' '\n+\ttest_write_lines a b c >pre &&\n+\ttest_write_lines c a b >post &&\n+\n+\t# normally, c is moved to produce the smallest diff\n+\ttest_expect_code 1 git diff --no-index pre post >diff &&\n+\tgrep \"^+c\" diff &&\n+\n+\t# with anchor, a is moved\n+\ttest_expect_code 1 git diff --no-index --anchored=c pre post >diff &&\n+\tgrep \"^+a\" diff\n+'\n+\n+test_expect_success '--anchored multiple' '\n+\ttest_write_lines a b c d e f >pre &&\n+\ttest_write_lines c a b f d e >post &&\n+\n+\t# with 1 anchor, c is not moved, but f is moved\n+\ttest_expect_code 1 git diff --no-index --anchored=c pre post >diff &&\n+\tgrep \"^+a\" diff && # a is moved instead of c\n+\tgrep \"^+f\" diff &&\n+\n+\t# with 2 anchors, c and f are not moved\n+\ttest_expect_code 1 git diff --no-index --anchored=c --anchored=f pre post >diff &&\n+\tgrep \"^+a\" diff &&\n+\tgrep \"^+d\" diff # d is moved instead of f\n+'\n+\n+test_expect_success '--anchored with nonexistent line has no effect' '\n+\ttest_write_lines a b c >pre &&\n+\ttest_write_lines c a b >post &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=x pre post >diff &&\n+\tgrep \"^+c\" diff\n+'\n+\n+test_expect_success '--anchored with non-unique line has no effect' '\n+\ttest_write_lines a b c d e c >pre &&\n+\ttest_write_lines c a b c d e >post &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=c pre post >diff &&\n+\tgrep \"^+c\" diff\n+'\n+\n+test_expect_success 'diff still produced with impossible multiple --anchored' '\n+\ttest_write_lines a b c >pre &&\n+\ttest_write_lines c a b >post &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=a --anchored=c pre post >diff &&\n+\tmv post expected_post &&\n+\n+\t# Ensure that the diff is correct by applying it and then\n+\t# comparing the result with the original\n+\tgit apply diff &&\n+\tdiff expected_post post\n+'\n+\n+test_expect_success 'later algorithm arguments override earlier ones' '\n+\ttest_write_lines a b c >pre &&\n+\ttest_write_lines c a b >post &&\n+\n+\ttest_expect_code 1 git diff --no-index --patience --anchored=c pre post >diff &&\n+\tgrep \"^+a\" diff &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=c --patience pre post >diff &&\n+\tgrep \"^+c\" diff &&\n+\n+\ttest_expect_code 1 git diff --no-index --histogram --anchored=c pre post >diff &&\n+\tgrep \"^+a\" diff &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=c --histogram pre post >diff &&\n+\tgrep \"^+c\" diff &&\n+\n+\ttest_expect_code 1 git diff --no-index --diff-algorithm=patience --anchored=c pre post >diff &&\n+\tgrep \"^+a\" diff &&\n+\n+\ttest_expect_code 1 git diff --no-index --anchored=c --diff-algorithm=patience pre post >diff &&\n+\tgrep \"^+c\" diff\n+'\n+\n+test_expect_success '--anchored works with other commands like \"git show\"' '\n+\ttest_write_lines a b c >file &&\n+\tgit add file &&\n+\tgit commit -m foo &&\n+\ttest_write_lines c a b >file &&\n+\tgit add file &&\n+\tgit commit -m foo &&\n+\n+\t# with anchor, a is moved\n+\tgit show --patience --anchored=c >diff &&\n+\tgrep \"^+a\" diff\n+'\n+\n+test_done\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 785ecb089..e6217e1d7 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -80,6 +80,10 @@ typedef struct s_mmbuffer {\n \n typedef struct s_xpparam {\n \tunsigned long flags;\n+\n+\t/* See Documentation/diff-options.txt. */\n+\tchar **anchors;\n+\tsize_t anchors_nr;\n } xpparam_t;\n \n typedef struct s_xdemitcb {\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex a44e77632..f3573d9f0 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -62,6 +62,12 @@ struct hashmap {\n \t\t * initially, \"next\" reflects only the order in file1.\n \t\t */\n \t\tstruct entry *next, *previous;\n+\n+\t\t/*\n+\t\t * If 1, this entry can serve as an anchor. See\n+\t\t * Documentation/diff-options.txt for more information.\n+\t\t */\n+\t\tunsigned anchor : 1;\n \t} *entries, *first, *last;\n \t/* were common records found? */\n \tunsigned long has_matches;\n@@ -70,8 +76,19 @@ struct hashmap {\n \txpparam_t const *xpp;\n };\n \n+static int is_anchor(xpparam_t const *xpp, const char *line)\n+{\n+\tint i;\n+\tfor (i = 0; i < xpp->anchors_nr; i++) {\n+\t\tif (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i])))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n /* The argument \"pass\" is 1 for the first file, 2 for the second. */\n-static void insert_record(int line, struct hashmap *map, int pass)\n+static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n+\t\t\t  int pass)\n {\n \txrecord_t **records = pass == 1 ?\n \t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n@@ -110,6 +127,7 @@ static void insert_record(int line, struct hashmap *map, int pass)\n \t\treturn;\n \tmap->entries[index].line1 = line;\n \tmap->entries[index].hash = record->ha;\n+\tmap->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr);\n \tif (!map->first)\n \t\tmap->first = map->entries + index;\n \tif (map->last) {\n@@ -147,11 +165,11 @@ static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,\n \n \t/* First, fill with entries from the first file */\n \twhile (count1--)\n-\t\tinsert_record(line1++, result, 1);\n+\t\tinsert_record(xpp, line1++, result, 1);\n \n \t/* Then search for matches in the second file */\n \twhile (count2--)\n-\t\tinsert_record(line2++, result, 2);\n+\t\tinsert_record(xpp, line2++, result, 2);\n \n \treturn 0;\n }\n@@ -192,14 +210,28 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)\n \tint longest = 0, i;\n \tstruct entry *entry;\n \n+\t/*\n+\t * If not -1, this entry in sequence must never be overridden.\n+\t * Therefore, overriding entries before this has no effect, so\n+\t * do not do that either.\n+\t */\n+\tint anchor_i = -1;\n+\n \tfor (entry = map->first; entry; entry = entry->next) {\n \t\tif (!entry->line2 || entry->line2 == NON_UNIQUE)\n \t\t\tcontinue;\n \t\ti = binary_search(sequence, longest, entry);\n \t\tentry->previous = i < 0 ? NULL : sequence[i];\n-\t\tsequence[++i] = entry;\n-\t\tif (i == longest)\n+\t\t++i;\n+\t\tif (i <= anchor_i)\n+\t\t\tcontinue;\n+\t\tsequence[i] = entry;\n+\t\tif (entry->anchor) {\n+\t\t\tanchor_i = i;\n+\t\t\tlongest = anchor_i + 1;\n+\t\t} else if (i == longest) {\n \t\t\tlongest++;\n+\t\t}\n \t}\n \n \t/* No common unique lines were found */\n-- \n2.15.0.417.g466bffb3ac-goog\n\n"},{"id":"333824","messageId":"alpine.DEB.2.21.1.1711300134560.6482@virtualbox","threadId":"47286","inReplyTo":"20171128184703.155931-1-jonathantanmy@google.com","subject":"Re: [PATCH v3] diff: support anchoring line(s)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-11-30T00:36:37Z","receivedAt":"2017-11-30T00:36:48Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Jonathan,\n\nOn Tue, 28 Nov 2017, Jonathan Tan wrote:\n\n> @@ -4607,7 +4627,14 @@ int diff_opt_parse(struct diff_options *options,\n>  \t\tDIFF_XDL_CLR(options, NEED_MINIMAL);\n>  \t\toptions->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;\n>  \t\toptions->xdl_opts |= value;\n> +\t\tif (value == XDF_PATIENCE_DIFF)\n> +\t\t\tclear_patience_anchors(options);\n>  \t\treturn argcount;\n> +\t} else if (skip_prefix(arg, \"--anchored=\", &arg)) {\n> +\t\toptions->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);\n> +\t\tALLOC_GROW(options->anchors, options->anchors_nr + 1,\n> +\t\t\t   options->anchors_alloc);\n> +\t\toptions->anchors[options->anchors_nr++] = xstrdup(arg);\n\nI looked and failed to find the code that releases this array after the\ndiff is done... did I miss anything?\n\nCiao,\nDscho\n"},{"id":"333876","messageId":"20171130152605.1b775e9cc2ddd7f917424448@google.com","threadId":"47286","inReplyTo":"alpine.DEB.2.21.1.1711300134560.6482@virtualbox","subject":"Re: [PATCH v3] diff: support anchoring line(s)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-11-30T23:26:05Z","receivedAt":"2017-11-30T23:26:13Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Thu, 30 Nov 2017 01:36:37 +0100 (CET)\nJohannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n\n> Hi Jonathan,\n> \n> On Tue, 28 Nov 2017, Jonathan Tan wrote:\n> \n> > @@ -4607,7 +4627,14 @@ int diff_opt_parse(struct diff_options *options,\n> >  \t\tDIFF_XDL_CLR(options, NEED_MINIMAL);\n> >  \t\toptions->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;\n> >  \t\toptions->xdl_opts |= value;\n> > +\t\tif (value == XDF_PATIENCE_DIFF)\n> > +\t\t\tclear_patience_anchors(options);\n> >  \t\treturn argcount;\n> > +\t} else if (skip_prefix(arg, \"--anchored=\", &arg)) {\n> > +\t\toptions->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);\n> > +\t\tALLOC_GROW(options->anchors, options->anchors_nr + 1,\n> > +\t\t\t   options->anchors_alloc);\n> > +\t\toptions->anchors[options->anchors_nr++] = xstrdup(arg);\n> \n> I looked and failed to find the code that releases this array after the\n> diff is done... did I miss anything?\n\nYou didn't miss anything. As far as I can tell, occurrences of struct\ndiff_options live throughout the lifetime of an invocation of Git and\nare not freed. (Even if the struct itself is allocated on the stack, its\npathspec has some elements allocated on the heap.)\n"},{"id":"334082","messageId":"CAGZ79kZ7EvpOUgdkMe=+nx1qV23jvDaY4-GVzjmtN_hnJ71bag@mail.gmail.com","threadId":"47286","inReplyTo":"20171130152605.1b775e9cc2ddd7f917424448@google.com","subject":"Re: [PATCH v3] diff: support anchoring line(s)","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-12-04T19:45:34Z","receivedAt":"2017-12-04T19:45:42Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Nov 30, 2017 at 3:26 PM, Jonathan Tan <jonathantanmy@google.com> wrote:\n> On Thu, 30 Nov 2017 01:36:37 +0100 (CET)\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n>\n>> Hi Jonathan,\n>>\n>> On Tue, 28 Nov 2017, Jonathan Tan wrote:\n>>\n>> > @@ -4607,7 +4627,14 @@ int diff_opt_parse(struct diff_options *options,\n>> >             DIFF_XDL_CLR(options, NEED_MINIMAL);\n>> >             options->xdl_opts &= ~XDF_DIFF_ALGORITHM_MASK;\n>> >             options->xdl_opts |= value;\n>> > +           if (value == XDF_PATIENCE_DIFF)\n>> > +                   clear_patience_anchors(options);\n>> >             return argcount;\n>> > +   } else if (skip_prefix(arg, \"--anchored=\", &arg)) {\n>> > +           options->xdl_opts = DIFF_WITH_ALG(options, PATIENCE_DIFF);\n>> > +           ALLOC_GROW(options->anchors, options->anchors_nr + 1,\n>> > +                      options->anchors_alloc);\n>> > +           options->anchors[options->anchors_nr++] = xstrdup(arg);\n>>\n>> I looked and failed to find the code that releases this array after the\n>> diff is done... did I miss anything?\n>\n> You didn't miss anything. As far as I can tell, occurrences of struct\n> diff_options live throughout the lifetime of an invocation of Git and\n> are not freed. (Even if the struct itself is allocated on the stack, its\n> pathspec has some elements allocated on the heap.)\n\nI thought at least for the intra-line word diff, which allocates its own\ndiff options struct, we'd clear them, but looking around we seem to leak\nthe diff options consistently. (builtin/blame.c is nice enough to\n`clear_pathspec(&diff_opts.pathspec)`, but that's about it, no other\ncommand takes care of the cruft.\n\nI wonder if diff_flush might be a good place to clean up the diff options\nand after the flush the diff options are declared invalid?\n\n> test_expect_success '--anchored with non-unique line has no effect'\n\nokay, if it turns out we need this case in the future we can still come up\nwith ideas.\n\nThanks,\nStefan\n"}]}