{"thread":{"id":"44004","subject":"[PATCHv3] diff.c: emit moved lines with a different color","startedAt":"2016-09-04T23:43:57Z","lastAt":"2016-09-07T21:21:38Z","messageCount":7,"participants":["Stefan Beller","Jacob Keller","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"301077","messageId":"20160904234237.10548-1-stefanbeller@gmail.com","threadId":"44004","inReplyTo":null,"subject":"[PATCHv3] diff.c: emit moved lines with a different color","fromName":"Stefan Beller","fromEmail":"stefanbeller@gmail.com","sentAt":"2016-09-04T23:42:37Z","receivedAt":"2016-09-04T23:43:57Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"When we color the diff, we'll mark moved lines with a different color.\n\nThis is achieved by doing a two passes over the diff. The first pass\nwill inspect each line of the diff and store the removed lines and the\nadded lines in its own hash map.\nThe second pass will check for each added line if that is found in the\nset of removed lines. If so it will color the added line differently as\nwith the new `moved-new` color mode. For each removed line we check the\nset of added lines and if found emit that with the new color `moved-old`.\n\nWhen detecting the moved lines, we cannot just rely on a line being equal,\nbut we need to take the context into account to detect when the moves were\nreordered as we do not want to color moved but per-mutated lines.\nTo do that we use the hash of the preceding line.\n\nThis patch was motivated by e.g. reviewing 3b0c4200 (\"apply: move\nlibified code from builtin/apply.c to apply.{c,h}\", 2016-08-08)\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n\n * fixed memleaks\n * only run the new code when needed.\n * renamed variables to fit in better.\n\n\n Documentation/config.txt               |   5 +-\n contrib/completion/git-completion.bash |   2 +\n diff.c                                 | 200 +++++++++++++++++++++++++++++++--\n diff.h                                 |   5 +-\n 4 files changed, 202 insertions(+), 10 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 0bcb679..f4f51c2 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -980,8 +980,9 @@ color.diff.<slot>::\n \tof `context` (context text - `plain` is a historical synonym),\n \t`meta` (metainformation), `frag`\n \t(hunk header), 'func' (function in hunk header), `old` (removed lines),\n-\t`new` (added lines), `commit` (commit headers), or `whitespace`\n-\t(highlighting whitespace errors).\n+\t`new` (added lines), `commit` (commit headers), `whitespace`\n+\t(highlighting whitespace errors), `moved-old` (removed lines that\n+\treappear), `moved-new` (added lines that were removed elsewhere).\n \n color.decorate.<slot>::\n \tUse customized color for 'git log --decorate' output.  `<slot>` is one\ndiff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash\nindex 9c8f738..b558d12 100644\n--- a/contrib/completion/git-completion.bash\n+++ b/contrib/completion/git-completion.bash\n@@ -2115,6 +2115,8 @@ _git_config ()\n \t\tcolor.diff.old\n \t\tcolor.diff.plain\n \t\tcolor.diff.whitespace\n+\t\tcolor.diff.moved-old\n+\t\tcolor.diff.moved-new\n \t\tcolor.grep\n \t\tcolor.grep.context\n \t\tcolor.grep.filename\ndiff --git a/diff.c b/diff.c\nindex 534c12e..7fde014 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -18,6 +18,7 @@\n #include \"ll-merge.h\"\n #include \"string-list.h\"\n #include \"argv-array.h\"\n+#include \"git-compat-util.h\"\n \n #ifdef NO_FAST_WORKING_DIRECTORY\n #define FAST_WORKING_DIRECTORY 0\n@@ -42,6 +43,16 @@ static int diff_dirstat_permille_default = 30;\n static struct diff_options default_diff_options;\n static long diff_algorithm;\n \n+static struct hashmap *moved_add;\n+static struct hashmap *moved_del;\n+static int hash_prev_added;\n+static int hash_prev_removed;\n+struct moved_entry {\n+\tstruct hashmap_entry ent;\n+\tchar *line;\n+\tint hash_prev_line;\n+};\n+\n static char diff_colors[][COLOR_MAXLEN] = {\n \tGIT_COLOR_RESET,\n \tGIT_COLOR_NORMAL,\t/* CONTEXT */\n@@ -52,6 +63,8 @@ static char diff_colors[][COLOR_MAXLEN] = {\n \tGIT_COLOR_YELLOW,\t/* COMMIT */\n \tGIT_COLOR_BG_RED,\t/* WHITESPACE */\n \tGIT_COLOR_NORMAL,\t/* FUNCINFO */\n+\tGIT_COLOR_BLUE,\t\t/* NEW MOVED */\n+\tGIT_COLOR_MAGENTA,\t/* OLD MOVED */\n };\n \n static int parse_diff_color_slot(const char *var)\n@@ -72,6 +85,10 @@ static int parse_diff_color_slot(const char *var)\n \t\treturn DIFF_WHITESPACE;\n \tif (!strcasecmp(var, \"func\"))\n \t\treturn DIFF_FUNCINFO;\n+\tif (!strcasecmp(var, \"moved-old\"))\n+\t\treturn DIFF_FILE_MOVED_OLD;\n+\tif (!strcasecmp(var, \"moved-new\"))\n+\t\treturn DIFF_FILE_MOVED_NEW;\n \treturn -1;\n }\n \n@@ -287,6 +304,25 @@ int git_diff_basic_config(const char *var, const char *value, void *cb)\n \treturn git_default_config(var, value, cb);\n }\n \n+static int moved_entry_cmp(const struct moved_entry *a,\n+\t\t\t   const struct moved_entry *b,\n+\t\t\t   const void *unused)\n+{\n+\treturn strcmp(a->line, b->line) &&\n+\t       a->hash_prev_line == b->hash_prev_line;\n+}\n+\n+static struct moved_entry *prepare_entry(const char *line,\n+\t\t\t\t\t unsigned long len,\n+\t\t\t\t\t int hash_prev_line)\n+{\n+\tstruct moved_entry *ret = xmalloc(sizeof(*ret));\n+\tret->ent.hash = memhash(line, len) ^ hash_prev_line;\n+\tret->line = xmemdupz(line, len);\n+\tret->hash_prev_line = hash_prev_line;\n+\treturn ret;\n+}\n+\n static char *quote_two(const char *one, const char *two)\n {\n \tint need_one = quote_c_style(one, NULL, NULL, 1);\n@@ -537,16 +573,38 @@ static void emit_add_line(const char *reset,\n \t\t\t  struct emit_callback *ecbdata,\n \t\t\t  const char *line, int len)\n {\n+\tenum color_diff color = DIFF_FILE_NEW;\n+\tunsigned ws_error_highlight = WSEH_NEW;\n+\n+\tif (ecbdata->opt->color_moved) {\n+\t\tint hash = memhash(line, len);\n+\t\tstruct moved_entry *keydata = prepare_entry(line, len,\n+\t\t\t\t\t\t\t    hash_prev_added);\n+\t\tif (hashmap_get(moved_del, keydata, keydata))\n+\t\t\tcolor = DIFF_FILE_MOVED_NEW;\n+\t\thash_prev_added = hash;\n+\t}\n \temit_line_checked(reset, ecbdata, line, len,\n-\t\t\t  DIFF_FILE_NEW, WSEH_NEW, '+');\n+\t\t\t  color, ws_error_highlight, '+');\n }\n \n static void emit_del_line(const char *reset,\n \t\t\t  struct emit_callback *ecbdata,\n \t\t\t  const char *line, int len)\n {\n+\tenum color_diff color = DIFF_FILE_OLD;\n+\tunsigned ws_error_highlight = WSEH_OLD;\n+\n+\tif (ecbdata->opt->color_moved) {\n+\t\tint hash = memhash(line, len);\n+\t\tstruct moved_entry *keydata = prepare_entry(line, len,\n+\t\t\t\t\t\t\t    hash_prev_removed);\n+\t\tif (hashmap_get(moved_add, keydata, keydata))\n+\t\t\tcolor = DIFF_FILE_MOVED_OLD;\n+\t\thash_prev_removed = hash;\n+\t}\n \temit_line_checked(reset, ecbdata, line, len,\n-\t\t\t  DIFF_FILE_OLD, WSEH_OLD, '-');\n+\t\t\t  color, ws_error_highlight, '-');\n }\n \n static void emit_context_line(const char *reset,\n@@ -555,6 +613,11 @@ static void emit_context_line(const char *reset,\n {\n \temit_line_checked(reset, ecbdata, line, len,\n \t\t\t  DIFF_CONTEXT, WSEH_CONTEXT, ' ');\n+\tif (ecbdata->opt->color_moved) {\n+\t\tint h = memhash(line, len);\n+\t\thash_prev_removed = h;\n+\t\thash_prev_added = h;\n+\t}\n }\n \n static void emit_hunk_header(struct emit_callback *ecbdata,\n@@ -1323,6 +1386,41 @@ static void fn_out_consume(void *priv, char *line, unsigned long len)\n \t}\n }\n \n+static void fn_prepare_consume(void *priv, char *line, unsigned long len)\n+{\n+\tstruct moved_entry *d;\n+\tint hash = memhash(line + 1, len - 1);\n+\n+\tswitch (line[0]) {\n+\tcase ' ':\n+\t\thashmap_add(moved_del, prepare_entry(line + 1, len - 1, 0));\n+\t\thashmap_add(moved_add, prepare_entry(line + 1, len - 1, 0));\n+\t\thash_prev_added = hash;\n+\t\thash_prev_removed = hash;\n+\t\tbreak;\n+\tcase '+':\n+\t\tif (hash_prev_added) {\n+\t\t\td = prepare_entry(line + 1, len - 1, hash_prev_added);\n+\t\t\thashmap_add(moved_add, d);\n+\t\t}\n+\t\thash_prev_added = hash;\n+\t\thash_prev_removed = 0;\n+\t\tbreak;\n+\tcase '-':\n+\t\tif (hash_prev_removed) {\n+\t\t\td = prepare_entry(line + 1, len - 1, hash_prev_removed);\n+\t\t\thashmap_add(moved_del, d);\n+\t\t}\n+\t\thash_prev_added = 0;\n+\t\thash_prev_removed = hash;\n+\t\tbreak;\n+\tdefault:\n+\t\thash_prev_added = 0;\n+\t\thash_prev_removed = 0;\n+\t\tbreak;\n+\t}\n+}\n+\n static char *pprint_rename(const char *a, const char *b)\n {\n \tconst char *old = a;\n@@ -2279,6 +2377,56 @@ struct userdiff_driver *get_textconv(struct diff_filespec *one)\n \treturn userdiff_get_textconv(one->driver);\n }\n \n+static void prepare_moved_lines(struct diff_filepair *p, struct diff_options *o)\n+{\n+\tmmfile_t mf1, mf2;\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n+\tstruct emit_callback ecbdata;\n+\tstruct diff_filespec *one = p->one;\n+\tstruct diff_filespec *two = p->two;\n+\tstruct userdiff_driver *textconv_one = NULL;\n+\tstruct userdiff_driver *textconv_two = NULL;\n+\n+\tif ((!one->mode || S_ISGITLINK(one->mode)) ||\n+\t    (!two->mode || S_ISGITLINK(two->mode)))\n+\t\treturn;\n+\n+\tif (DIFF_OPT_TST(o, ALLOW_TEXTCONV)) {\n+\t\ttextconv_one = get_textconv(one);\n+\t\ttextconv_two = get_textconv(two);\n+\t}\n+\n+\tif (!DIFF_OPT_TST(o, TEXT) &&\n+\t    ( (!textconv_one && diff_filespec_is_binary(one)) ||\n+\t      (!textconv_two && diff_filespec_is_binary(two)) ))\n+\t      return;\n+\n+\tmf1.size = fill_textconv(textconv_one, one, &mf1.ptr);\n+\tmf2.size = fill_textconv(textconv_two, two, &mf2.ptr);\n+\n+\tmemset(&xpp, 0, sizeof(xpp));\n+\tmemset(&xecfg, 0, sizeof(xecfg));\n+\tmemset(&ecbdata, 0, sizeof(ecbdata));\n+\n+\txpp.flags = o->xdl_opts;\n+\txecfg.ctxlen = 1;\n+\n+\tif (o->word_diff)\n+\t\tinit_diff_words_data(&ecbdata, o, one, two);\n+\tif (xdi_diff_outf(&mf1, &mf2, fn_prepare_consume, &ecbdata,\n+\t\t\t  &xpp, &xecfg))\n+\t\tdie(\"unable to generate generate moved color output for %s\",\n+\t\t    one->path);\n+\tif (o->word_diff)\n+\t\tfree_diff_words_data(&ecbdata);\n+\tif (textconv_one)\n+\t\tfree(mf1.ptr);\n+\tif (textconv_two)\n+\t\tfree(mf2.ptr);\n+\txdiff_clear_find_func(&xecfg);\n+}\n+\n static void builtin_diff(const char *name_a,\n \t\t\t const char *name_b,\n \t\t\t struct diff_filespec *one,\n@@ -3295,6 +3443,7 @@ void diff_setup(struct diff_options *options)\n \toptions->xdl_opts |= diff_algorithm;\n \tif (diff_compaction_heuristic)\n \t\tDIFF_XDL_SET(options, COMPACTION_HEURISTIC);\n+\toptions->color_moved = options->use_color;\n \n \toptions->orderfile = diff_order_file_cfg;\n \n@@ -3413,6 +3562,9 @@ void diff_setup_done(struct diff_options *options)\n \n \tif (DIFF_OPT_TST(options, FOLLOW_RENAMES) && options->pathspec.nr != 1)\n \t\tdie(_(\"--follow requires exactly one pathspec\"));\n+\n+\tif (!options->use_color || external_diff())\n+\t\toptions->color_moved = 0;\n }\n \n static int opt_arg(const char *arg, int arg_short, const char *arg_long, int *val)\n@@ -4622,6 +4774,43 @@ void diff_warn_rename_limit(const char *varname, int needed, int degraded_cc)\n \t\twarning(rename_limit_advice, varname, needed);\n }\n \n+static void diff_flush_format_patch(struct diff_options *o)\n+{\n+\tint i;\n+\tstruct diff_queue_struct *q = &diff_queued_diff;\n+\tif (o->color_moved) {\n+\t\tmoved_add = xmalloc(sizeof(*moved_add));\n+\t\tmoved_del = xmalloc(sizeof(*moved_del));\n+\t\thashmap_init(moved_add, (hashmap_cmp_fn)moved_entry_cmp, 0);\n+\t\thashmap_init(moved_del, (hashmap_cmp_fn)moved_entry_cmp, 0);\n+\n+\t\tfor (i = 0; i < q->nr; i++) {\n+\t\t\tstruct diff_filepair *p = q->queue[i];\n+\t\t\tif (check_pair_status(p) && !diff_unmodified_pair(p))\n+\t\t\t\tprepare_moved_lines(p, o);\n+\t\t}\n+\t}\n+\n+\tfor (i = 0; i < q->nr; i++) {\n+\t\tstruct diff_filepair *p = q->queue[i];\n+\t\tif (check_pair_status(p))\n+\t\t\tdiff_flush_patch(p, o);\n+\t}\n+\n+\tif (o->color_moved) {\n+\t\tstruct hashmap_iter iter;\n+\t\tstruct moved_entry *e;\n+\t\thashmap_iter_init(moved_add, &iter);\n+\t\twhile ((e = hashmap_iter_next(&iter)))\n+\t\t\tfree(e->line);\n+\t\thashmap_iter_init(moved_del, &iter);\n+\t\twhile ((e = hashmap_iter_next(&iter)))\n+\t\t\tfree(e->line);\n+\t\thashmap_free(moved_add, 1);\n+\t\thashmap_free(moved_del, 1);\n+\t}\n+}\n+\n void diff_flush(struct diff_options *options)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n@@ -4696,6 +4885,7 @@ void diff_flush(struct diff_options *options)\n \t\tif (!options->file)\n \t\t\tdie_errno(\"Could not open /dev/null\");\n \t\toptions->close_file = 1;\n+\t\toptions->color_moved = 0;\n \t\tfor (i = 0; i < q->nr; i++) {\n \t\t\tstruct diff_filepair *p = q->queue[i];\n \t\t\tif (check_pair_status(p))\n@@ -4716,11 +4906,7 @@ void diff_flush(struct diff_options *options)\n \t\t\t}\n \t\t}\n \n-\t\tfor (i = 0; i < q->nr; i++) {\n-\t\t\tstruct diff_filepair *p = q->queue[i];\n-\t\t\tif (check_pair_status(p))\n-\t\t\t\tdiff_flush_patch(p, options);\n-\t\t}\n+\t\tdiff_flush_format_patch(options);\n \t}\n \n \tif (output_format & DIFF_FORMAT_CALLBACK)\ndiff --git a/diff.h b/diff.h\nindex 7883729..b0331b9 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -122,6 +122,7 @@ struct diff_options {\n \tunsigned int filter;\n \n \tint use_color;\n+\tint color_moved;\n \tint context;\n \tint interhunkcontext;\n \tint break_opt;\n@@ -189,7 +190,9 @@ enum color_diff {\n \tDIFF_FILE_NEW = 5,\n \tDIFF_COMMIT = 6,\n \tDIFF_WHITESPACE = 7,\n-\tDIFF_FUNCINFO = 8\n+\tDIFF_FUNCINFO = 8,\n+\tDIFF_FILE_MOVED_NEW = 9,\n+\tDIFF_FILE_MOVED_OLD = 10\n };\n const char *diff_get_color(int diff_use_color, enum color_diff ix);\n #define diff_get_color_opt(o, ix) \\\n-- \n2.10.0.1.ga424fb3\n\n"},{"id":"301158","messageId":"CA+P7+xr=Lp36wDw2BRuhQ9Genv4q6iu9beGQe5hzOn5PJYDPfw@mail.gmail.com","threadId":"44004","inReplyTo":"20160904234237.10548-1-stefanbeller@gmail.com","subject":"Re: [PATCHv3] diff.c: emit moved lines with a different color","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-09-06T01:17:51Z","receivedAt":"2016-09-06T01:18:17Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Sun, Sep 4, 2016 at 4:42 PM, Stefan Beller <stefanbeller@gmail.com> wrote:\n> When we color the diff, we'll mark moved lines with a different color.\n>\n\nExcellent idea. This is a very neat way to show extra information\nwithout cluttering the diff output.\n\n> This is achieved by doing a two passes over the diff. The first pass\n> will inspect each line of the diff and store the removed lines and the\n> added lines in its own hash map.\n> The second pass will check for each added line if that is found in the\n> set of removed lines. If so it will color the added line differently as\n> with the new `moved-new` color mode. For each removed line we check the\n> set of added lines and if found emit that with the new color `moved-old`.\n>\n\nMakes sense.\n\n> When detecting the moved lines, we cannot just rely on a line being equal,\n> but we need to take the context into account to detect when the moves were\n> reordered as we do not want to color moved but per-mutated lines.\n> To do that we use the hash of the preceding line.\n\nAlso makes sense.\n\n>\n> This patch was motivated by e.g. reviewing 3b0c4200 (\"apply: move\n> libified code from builtin/apply.c to apply.{c,h}\", 2016-08-08)\n>\n\nYes, this would be quite helpful.\n\n> diff --git a/Documentation/config.txt b/Documentation/config.txt\n> index 0bcb679..f4f51c2 100644\n> --- a/Documentation/config.txt\n> +++ b/Documentation/config.txt\n> @@ -980,8 +980,9 @@ color.diff.<slot>::\n>         of `context` (context text - `plain` is a historical synonym),\n>         `meta` (metainformation), `frag`\n>         (hunk header), 'func' (function in hunk header), `old` (removed lines),\n> -       `new` (added lines), `commit` (commit headers), or `whitespace`\n> -       (highlighting whitespace errors).\n> +       `new` (added lines), `commit` (commit headers), `whitespace`\n> +       (highlighting whitespace errors), `moved-old` (removed lines that\n> +       reappear), `moved-new` (added lines that were removed elsewhere).\n>\n\nI liked Junio's \"Moved from\" and \"moved to\" but I think moved old and\nmoved new are ok as well.\n\n> @@ -287,6 +304,25 @@ int git_diff_basic_config(const char *var, const char *value, void *cb)\n>         return git_default_config(var, value, cb);\n>  }\n>\n> +static int moved_entry_cmp(const struct moved_entry *a,\n> +                          const struct moved_entry *b,\n> +                          const void *unused)\n> +{\n> +       return strcmp(a->line, b->line) &&\n> +              a->hash_prev_line == b->hash_prev_line;\n\nSo we're only comparing them if they match and have a matching\nprevious line? That seems pretty reasonable to reduce the cost of\ncomputing exact copied sequences.\n\n> +       if (ecbdata->opt->color_moved) {\n> +               int h = memhash(line, len);\n> +               hash_prev_removed = h;\n> +               hash_prev_added = h;\n> +       }\n>  }\n\nIf I understand, this is to ensure that we don't keep re-hashing each\nline right?\n\nThanks,\nJake\n"},{"id":"301161","messageId":"CAGZ79ka7VV6Pqw-rcVFv0xU4J4D9dHWPg-oocPPWJdY5JVhT+A@mail.gmail.com","threadId":"44004","inReplyTo":"CA+P7+xr=Lp36wDw2BRuhQ9Genv4q6iu9beGQe5hzOn5PJYDPfw@mail.gmail.com","subject":"Re: [PATCHv3] diff.c: emit moved lines with a different color","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-09-06T02:20:07Z","receivedAt":"2016-09-06T02:20:14Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Sep 5, 2016 at 6:17 PM, Jacob Keller <jacob.keller@gmail.com> wrote:\n> On Sun, Sep 4, 2016 at 4:42 PM, Stefan Beller <stefanbeller@gmail.com> wrote:\n>> When we color the diff, we'll mark moved lines with a different color.\n>>\n>\n> Excellent idea. This is a very neat way to show extra information\n> without cluttering the diff output.\n>\n>> This is achieved by doing a two passes over the diff. The first pass\n>> will inspect each line of the diff and store the removed lines and the\n>> added lines in its own hash map.\n>> The second pass will check for each added line if that is found in the\n>> set of removed lines. If so it will color the added line differently as\n>> with the new `moved-new` color mode. For each removed line we check the\n>> set of added lines and if found emit that with the new color `moved-old`.\n>>\n>\n> Makes sense.\n>\n>> When detecting the moved lines, we cannot just rely on a line being equal,\n>> but we need to take the context into account to detect when the moves were\n>> reordered as we do not want to color moved but per-mutated lines.\n>> To do that we use the hash of the preceding line.\n>\n> Also makes sense.\n>\n>>\n>> This patch was motivated by e.g. reviewing 3b0c4200 (\"apply: move\n>> libified code from builtin/apply.c to apply.{c,h}\", 2016-08-08)\n>>\n>\n> Yes, this would be quite helpful.\n>\n>> diff --git a/Documentation/config.txt b/Documentation/config.txt\n>> index 0bcb679..f4f51c2 100644\n>> --- a/Documentation/config.txt\n>> +++ b/Documentation/config.txt\n>> @@ -980,8 +980,9 @@ color.diff.<slot>::\n>>         of `context` (context text - `plain` is a historical synonym),\n>>         `meta` (metainformation), `frag`\n>>         (hunk header), 'func' (function in hunk header), `old` (removed lines),\n>> -       `new` (added lines), `commit` (commit headers), or `whitespace`\n>> -       (highlighting whitespace errors).\n>> +       `new` (added lines), `commit` (commit headers), `whitespace`\n>> +       (highlighting whitespace errors), `moved-old` (removed lines that\n>> +       reappear), `moved-new` (added lines that were removed elsewhere).\n>>\n>\n> I liked Junio's \"Moved from\" and \"moved to\" but I think moved old and\n> moved new are ok as well.\n\nas we do not want to see dashes ('moved-old'), I think I'l go with\n\"movedfrom\" and \"movedto\".\n\n>\n>> @@ -287,6 +304,25 @@ int git_diff_basic_config(const char *var, const char *value, void *cb)\n>>         return git_default_config(var, value, cb);\n>>  }\n>>\n>> +static int moved_entry_cmp(const struct moved_entry *a,\n>> +                          const struct moved_entry *b,\n>> +                          const void *unused)\n>> +{\n>> +       return strcmp(a->line, b->line) &&\n>> +              a->hash_prev_line == b->hash_prev_line;\n>\n> So we're only comparing them if they match and have a matching\n> previous line? That seems pretty reasonable to reduce the cost of\n> computing exact copied sequences.\n>\n>> +       if (ecbdata->opt->color_moved) {\n>> +               int h = memhash(line, len);\n>> +               hash_prev_removed = h;\n>> +               hash_prev_added = h;\n>> +       }\n>>  }\n>\n> If I understand, this is to ensure that we don't keep re-hashing each\n> line right?\n\nNo, this is to ensure we have the context sensitivity of one prior line.\n\nIn the collection phase we look at each line of the patch and make a hash of it.\nThen we store the hash temporarily (think of a state machine that goes line by\nline and always keeps the hash of the last line)\n\nWhat we store in the hashmaps is the hash(current line) ^\nhash(previous applicable line).\nWith previous applicable line I mean any line starting with \" \" or \"+\"\nwhen the current\nline starts with \"+\" and \" \" or \"-\" when the current line starts with \"-\".\n\nWhen going through the second pass and actually emitting colored lines\nwe only find matches in the hash map if the current line AND the previous line\nmatch as we lookup by hash code, i.e. if we have a moved line, but the\nprevious line\nchanged we do not find it in the hashmap and we don't color it, such\nthat the reviewer\ncan spot a permutation.\n\nSo in the second phase we also need to have access to previous line, so maybe\nwe could also go with just taking the line with us instead of 2 hash codes.\nBut that implementation detail seems like a trade off to me, where I'd lean\non keeping the hashes around as lines may be very long in bad cases, whereas\nthe hashcode is short and it is a cheap hash.\n\n(I am referring to http://i.imgur.com/MnaSZ1D.png where in the malicious\ncase all lines were moved to there as well, but permutated)\n"},{"id":"301164","messageId":"CA+P7+xo9KqnjajkPbP9_Q2H6hHT47dqPX9i3e5hvm28a0JWJOQ@mail.gmail.com","threadId":"44004","inReplyTo":"CAGZ79ka7VV6Pqw-rcVFv0xU4J4D9dHWPg-oocPPWJdY5JVhT+A@mail.gmail.com","subject":"Re: [PATCHv3] diff.c: emit moved lines with a different color","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-09-06T06:58:15Z","receivedAt":"2016-09-06T06:58:40Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Mon, Sep 5, 2016 at 7:20 PM, Stefan Beller <sbeller@google.com> wrote:\n>> If I understand, this is to ensure that we don't keep re-hashing each\n>> line right?\n>\n> No, this is to ensure we have the context sensitivity of one prior line.\n>\n> In the collection phase we look at each line of the patch and make a hash of it.\n> Then we store the hash temporarily (think of a state machine that goes line by\n> line and always keeps the hash of the last line)\n>\n> What we store in the hashmaps is the hash(current line) ^\n> hash(previous applicable line).\n> With previous applicable line I mean any line starting with \" \" or \"+\"\n> when the current\n> line starts with \"+\" and \" \" or \"-\" when the current line starts with \"-\".\n>\n> When going through the second pass and actually emitting colored lines\n> we only find matches in the hash map if the current line AND the previous line\n> match as we lookup by hash code, i.e. if we have a moved line, but the\n> previous line\n> changed we do not find it in the hashmap and we don't color it, such\n> that the reviewer\n> can spot a permutation.\n>\n> So in the second phase we also need to have access to previous line, so maybe\n> we could also go with just taking the line with us instead of 2 hash codes.\n> But that implementation detail seems like a trade off to me, where I'd lean\n> on keeping the hashes around as lines may be very long in bad cases, whereas\n> the hashcode is short and it is a cheap hash.\n>\n> (I am referring to http://i.imgur.com/MnaSZ1D.png where in the malicious\n> case all lines were moved to there as well, but permutated)\n\nGood that clears up a lot of my questions. It seems like a reasonable\nalgorithm, and I like the example of per-muted lines.\n\nI think if we can find some real-world data on how much slower this\nis, we can find out what kind of configuration we want to give it? It\nseems like something incredibly helpful to me, but having a way out is\nnice incase it ends up being too costly. I suspect that will only be\nthe case for a large patch.\n\nThanks,\nJake\n"},{"id":"301300","messageId":"xmqq7fanoas6.fsf@gitster.mtv.corp.google.com","threadId":"44004","inReplyTo":"CAGZ79ka7VV6Pqw-rcVFv0xU4J4D9dHWPg-oocPPWJdY5JVhT+A@mail.gmail.com","subject":"Re: [PATCHv3] diff.c: emit moved lines with a different color","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-09-07T17:54:49Z","receivedAt":"2016-09-07T17:54:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> as we do not want to see dashes ('moved-old'), I think I'l go with\n> \"movedfrom\" and \"movedto\".\n\nOK.  They would be color.diff.movedFrom and color.diff.movedTo in\nthe doc, and \"movedfrom\" and \"movedto\" in the code (as the caller\nalready downcased them for you to strcmp()).\n\n> When going through the second pass and actually emitting colored lines\n> we only find matches in the hash map if the current line AND the previous line\n> match as we lookup by hash code, i.e. if we have a moved line, but the\n> previous line\n> changed we do not find it in the hashmap and we don't color it, such\n> that the reviewer\n> can spot a permutation.\n\nHmph.  Does this have impact on a line that was at the beginning or\nthe end of a file that got moved to the beginning or the end of a\nfile (four permutations, of 9 if you throw in \"middle\"), because\nsome cases it does not have a \"previous\" line?\n"},{"id":"301302","messageId":"CAGZ79kbSG-9xdmG3LWEsVoJnhEr5pcL8D-95E99a+=JaXGOXCA@mail.gmail.com","threadId":"44004","inReplyTo":"xmqq7fanoas6.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCHv3] diff.c: emit moved lines with a different color","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-09-07T18:02:17Z","receivedAt":"2016-09-07T18:02:23Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Sep 7, 2016 at 10:54 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Stefan Beller <sbeller@google.com> writes:\n>\n>> as we do not want to see dashes ('moved-old'), I think I'l go with\n>> \"movedfrom\" and \"movedto\".\n>\n> OK.  They would be color.diff.movedFrom and color.diff.movedTo in\n> the doc, and \"movedfrom\" and \"movedto\" in the code (as the caller\n> already downcased them for you to strcmp()).\n>\n>> When going through the second pass and actually emitting colored lines\n>> we only find matches in the hash map if the current line AND the previous line\n>> match as we lookup by hash code, i.e. if we have a moved line, but the\n>> previous line\n>> changed we do not find it in the hashmap and we don't color it, such\n>> that the reviewer\n>> can spot a permutation.\n>\n> Hmph.  Does this have impact on a line that was at the beginning or\n> the end of a file that got moved to the beginning or the end of a\n> file (four permutations, of 9 if you throw in \"middle\"), because\n> some cases it does not have a \"previous\" line?\n\nI spotted that problem as well. We need to adapt the algorithm a bit more:\n\n  If the previous line is of the same kind (i.e. starting with + or -),\n    then we have to take it into account,\n  otherwise (i.e. previous line is different, such as header, hunk header,\n  or different sign)\n    then ignore previous line, as the previous line is already\n    having a different color.\n\nThat works for the very first line of a file as well.\n"},{"id":"301326","messageId":"CA+P7+xp8KeeKY3jkWeSNzUvV1_cXOGpES4Ymj3BRTmM06jhY0Q@mail.gmail.com","threadId":"44004","inReplyTo":"CAGZ79kbSG-9xdmG3LWEsVoJnhEr5pcL8D-95E99a+=JaXGOXCA@mail.gmail.com","subject":"Re: [PATCHv3] diff.c: emit moved lines with a different color","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-09-07T21:21:12Z","receivedAt":"2016-09-07T21:21:38Z","isPatch":false,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Wed, Sep 7, 2016 at 11:02 AM, Stefan Beller <sbeller@google.com> wrote:\n> On Wed, Sep 7, 2016 at 10:54 AM, Junio C Hamano <gitster@pobox.com> wrote:\n>> Stefan Beller <sbeller@google.com> writes:\n>>\n>>> as we do not want to see dashes ('moved-old'), I think I'l go with\n>>> \"movedfrom\" and \"movedto\".\n>>\n>> OK.  They would be color.diff.movedFrom and color.diff.movedTo in\n>> the doc, and \"movedfrom\" and \"movedto\" in the code (as the caller\n>> already downcased them for you to strcmp()).\n>>\n>>> When going through the second pass and actually emitting colored lines\n>>> we only find matches in the hash map if the current line AND the previous line\n>>> match as we lookup by hash code, i.e. if we have a moved line, but the\n>>> previous line\n>>> changed we do not find it in the hashmap and we don't color it, such\n>>> that the reviewer\n>>> can spot a permutation.\n>>\n>> Hmph.  Does this have impact on a line that was at the beginning or\n>> the end of a file that got moved to the beginning or the end of a\n>> file (four permutations, of 9 if you throw in \"middle\"), because\n>> some cases it does not have a \"previous\" line?\n>\n> I spotted that problem as well. We need to adapt the algorithm a bit more:\n>\n>   If the previous line is of the same kind (i.e. starting with + or -),\n>     then we have to take it into account,\n>   otherwise (i.e. previous line is different, such as header, hunk header,\n>   or different sign)\n>     then ignore previous line, as the previous line is already\n>     having a different color.\n>\n> That works for the very first line of a file as well.\n\nThat should work to resolve some issues, and ensure the first line of\na hunk works correctly.\n\nThanks,\nJake\n"}]}