{"thread":{"id":"44002","subject":"[WIP PATCH v2] diff.c: emit moved lines with a different color","startedAt":"2016-09-04T19:14:54Z","lastAt":"2016-09-06T16:48:02Z","messageCount":7,"participants":["Stefan Beller","Junio C Hamano","Jacob Keller"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"301031","messageId":"20160904191435.14144-1-stefanbeller@gmail.com","threadId":"44002","inReplyTo":null,"subject":"[WIP PATCH v2] diff.c: emit moved lines with a different color","fromName":"Stefan Beller","fromEmail":"stefanbeller@gmail.com","sentAt":"2016-09-04T19:14:35Z","receivedAt":"2016-09-04T19:14:54Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"From: Stefan Beller <sbeller@google.com>\n\nWhen 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.\nFor each removed line we check the set of added lines and if found emit\nthat 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.\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  This adds code only in the diff_flush part, just as you suggested Junio.\n  \n  I think the design is sound now, as it produces good highlights across files;\n  though now the code still sucks.\n   * leaking memory; \n   * we run the code to detect moves more often than we need, e.g.\n     when we configured an external diff, we don't need to run it.\n     Or when we do not use colors at all.\n   * I need to think about if we need everything doubled for both add and\n       removal; maybe we can use one variable for both cases.\n\n\n  Jacob wrote:\n  \n  > In the example, the first and last lines of duplicate copies don't get\n  > colored differently, and that threw  me off. I feel like that was\n  > maybe not intentional? If it was, can you explain why?\n\n  We need the context to detect permutations, improved version:\n  \n  http://i.imgur.com/MnaSZ1D.png\n\n\n  Jakub wrote:\n  \n  > P.S. BTW. does this work with word-diff?\n  \n  No (not yet.... )\n  \n  Thanks,\n  Stefan\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, 205 insertions(+), 7 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..d37cb4f 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,11 @@ 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 *duplicates_added;\n+static struct hashmap *duplicates_removed;\n+static int hash_previous_line_added;\n+static int hash_previous_line_removed;\n+\n static char diff_colors[][COLOR_MAXLEN] = {\n \tGIT_COLOR_RESET,\n \tGIT_COLOR_NORMAL,\t/* CONTEXT */\n@@ -52,6 +58,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 +80,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 +299,30 @@ int git_diff_basic_config(const char *var, const char *value, void *cb)\n \treturn git_default_config(var, value, cb);\n }\n \n+struct dup_entry {\n+\tstruct hashmap_entry ent;\n+\tchar *line;\n+\tint previous_hash;\n+};\n+\n+static int dup_entry_cmp(const struct dup_entry *a,\n+\t\t\t const struct dup_entry *b,\n+\t\t\t const void *unused)\n+{\n+\treturn strcmp(a->line, b->line) && a->previous_hash == b->previous_hash;\n+}\n+\n+static struct dup_entry *prepare_entry(const char *line,\n+\t\t\t\t\tunsigned long len,\n+\t\t\t\t\tint previous_hash)\n+{\n+\tstruct dup_entry *ret = xmalloc(sizeof(*ret));\n+\tret->ent.hash = memhash(line, len) ^ previous_hash;\n+\tret->line = xmemdupz(line, len);\n+\tret->previous_hash = previous_hash;\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,46 @@ 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-\temit_line_checked(reset, ecbdata, line, len,\n-\t\t\t  DIFF_FILE_NEW, WSEH_NEW, '+');\n+\tif (!duplicates_removed) {\n+\t\temit_line_checked(reset, ecbdata, line, len,\n+\t\t\t\t  DIFF_FILE_NEW, WSEH_NEW, '+');\n+\t} else {\n+\t\tint hash = memhash(line, len);\n+\t\tstruct dup_entry *keydata = prepare_entry(line, len, hash_previous_line_added);\n+\t\tenum color_diff color = DIFF_FILE_NEW;\n+\t\tunsigned ws_error_highlight = WSEH_NEW;\n+\n+\t\tif (hashmap_get(duplicates_removed, keydata, keydata))\n+\t\t\tcolor = DIFF_FILE_MOVED_NEW;\n+\n+\t\temit_line_checked(reset, ecbdata, line, len,\n+\t\t\t\t  color, ws_error_highlight, '+');\n+\n+\t\thash_previous_line_added = hash;\n+\t}\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-\temit_line_checked(reset, ecbdata, line, len,\n-\t\t\t  DIFF_FILE_OLD, WSEH_OLD, '-');\n+\tif (!duplicates_added) {\n+\t\temit_line_checked(reset, ecbdata, line, len,\n+\t\t\t\t  DIFF_FILE_OLD, WSEH_OLD, '-');\n+\t} else {\n+\t\tint hash = memhash(line, len);\n+\t\tstruct dup_entry *keydata = prepare_entry(line, len, hash_previous_line_removed);\n+\t\tenum color_diff color = DIFF_FILE_OLD;\n+\t\tunsigned ws_error_highlight = WSEH_OLD;\n+\n+\t\tif (hashmap_get(duplicates_added, keydata, keydata))\n+\t\t\tcolor = DIFF_FILE_MOVED_OLD;\n+\n+\t\temit_line_checked(reset, ecbdata, line, len,\n+\t\t\t\t  color, ws_error_highlight, '-');\n+\n+\t\thash_previous_line_removed = hash;\n+\t}\n }\n \n static void emit_context_line(const char *reset,\n@@ -555,6 +621,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 (duplicates_added) {\n+\t\tint hash = memhash(line, len);\n+\t\thash_previous_line_removed = hash;\n+\t\thash_previous_line_added = hash;\n+\t}\n }\n \n static void emit_hunk_header(struct emit_callback *ecbdata,\n@@ -1323,6 +1394,59 @@ 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+\tint hash;\n+\tstruct dup_entry *d;\n+\n+\tif (!duplicates_added) {\n+\t\tduplicates_added = xmalloc(sizeof(*duplicates_added));\n+\t\tduplicates_removed = xmalloc(sizeof(*duplicates_removed));\n+\t\thashmap_init(duplicates_added, (hashmap_cmp_fn)dup_entry_cmp, 0);\n+\t\thashmap_init(duplicates_removed, (hashmap_cmp_fn)dup_entry_cmp, 0);\n+\t}\n+\n+\tswitch (line[0]) {\n+\tcase ' ':\n+\t\td = prepare_entry(line + 1, len - 1, 0);\n+\t\thashmap_add(duplicates_removed, d);\n+\t\thashmap_add(duplicates_added, d);\n+\t\tbreak;\n+\tcase '+':\n+\t\tif (hash_previous_line_added)\n+\t\t\thashmap_add(duplicates_added,\n+\t\t\t\tprepare_entry(line + 1, len - 1,\n+\t\t\t\t\t      hash_previous_line_added));\n+\t\tbreak;\n+\tcase '-':\n+\t\tif (hash_previous_line_removed)\n+\t\t\thashmap_add(duplicates_removed,\n+\t\t\t\tprepare_entry(line + 1, len - 1,\n+\t\t\t\t\t      hash_previous_line_removed));\n+\t\tbreak;\n+\t}\n+\n+\thash = memhash(line + 1, len - 1);\n+\tswitch (line[0]) {\n+\tcase ' ':\n+\t\thash_previous_line_added = hash;\n+\t\thash_previous_line_removed = hash;\n+\t\tbreak;\n+\tcase '+':\n+\t\thash_previous_line_added = hash;\n+\t\thash_previous_line_removed = 0;\n+\t\tbreak;\n+\tcase '-':\n+\t\thash_previous_line_added = 0;\n+\t\thash_previous_line_removed = hash;\n+\t\tbreak;\n+\tdefault:\n+\t\thash_previous_line_added = 0;\n+\t\thash_previous_line_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 +2403,50 @@ struct userdiff_driver *get_textconv(struct diff_filespec *one)\n \treturn userdiff_get_textconv(one->driver);\n }\n \n+\n+static void prepare_moved_lines(struct diff_filepair *p, struct diff_options *o)\n+{\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 (DIFF_OPT_TST(o, ALLOW_TEXTCONV)) {\n+\t\ttextconv_one = get_textconv(one);\n+\t\ttextconv_two = get_textconv(two);\n+\t}\n+\n+\t{\n+\t\tmmfile_t mf1, mf2;\n+\t\txpparam_t xpp;\n+\t\txdemitconf_t xecfg;\n+\t\tstruct emit_callback ecbdata;\n+\n+\t\tmf1.size = fill_textconv(textconv_one, one, &mf1.ptr);\n+\t\tmf2.size = fill_textconv(textconv_two, two, &mf2.ptr);\n+\n+\t\tmemset(&xpp, 0, sizeof(xpp));\n+\t\tmemset(&xecfg, 0, sizeof(xecfg));\n+\t\tmemset(&ecbdata, 0, sizeof(ecbdata));\n+\n+\t\txpp.flags = o->xdl_opts;\n+\t\txecfg.ctxlen = 1;\n+\n+\t\tif (o->word_diff)\n+\t\t\tinit_diff_words_data(&ecbdata, o, one, two);\n+\t\tif (xdi_diff_outf(&mf1, &mf2, fn_prepare_consume, &ecbdata,\n+\t\t\t\t  &xpp, &xecfg))\n+\t\t\tdie(\"unable to generate diff for %s\", one->path);\n+\t\tif (o->word_diff)\n+\t\t\tfree_diff_words_data(&ecbdata);\n+\t\tif (textconv_one)\n+\t\t\tfree(mf1.ptr);\n+\t\tif (textconv_two)\n+\t\t\tfree(mf2.ptr);\n+\t\txdiff_clear_find_func(&xecfg);\n+\t}\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 +3463,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->highlight_moved = options->use_color;\n \n \toptions->orderfile = diff_order_file_cfg;\n \n@@ -3413,6 +3582,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)\n+\t\toptions->highlight_moved = 0;\n }\n \n static int opt_arg(const char *arg, int arg_short, const char *arg_long, int *val)\n@@ -4622,6 +4794,24 @@ 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_maybe_prepare_moved_lines(struct diff_options *o)\n+{\n+\tint i;\n+\tstruct diff_queue_struct *q = &diff_queued_diff;\n+\tif (0\n+\t    /* TODO\n+\t     * internal diff and colored options, i.e.\n+\t     * only when we actually run into the emit_line_...\n+\t     * eventually */)\n+\t\treturn;\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\tprepare_moved_lines(p, o);\n+\t}\n+}\n+\n void diff_flush(struct diff_options *options)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n@@ -4716,6 +4906,8 @@ void diff_flush(struct diff_options *options)\n \t\t\t}\n \t\t}\n \n+\n+\t\tdiff_flush_maybe_prepare_moved_lines(options);\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))\ndiff --git a/diff.h b/diff.h\nindex 7883729..0e4367b 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -139,6 +139,7 @@ struct diff_options {\n \tint dirstat_permille;\n \tint setup;\n \tint abbrev;\n+\tint highlight_moved;\n /* white-space error highlighting */\n #define WSEH_NEW 1\n #define WSEH_CONTEXT 2\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.2.ga528ff4\n\n"},{"id":"301107","messageId":"xmqq1t0yqinr.fsf@gitster.mtv.corp.google.com","threadId":"44002","inReplyTo":"20160904191435.14144-1-stefanbeller@gmail.com","subject":"Re: [WIP PATCH v2] diff.c: emit moved lines with a different color","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-09-05T18:57:12Z","receivedAt":"2016-09-05T18:57:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <stefanbeller@gmail.com> writes:\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>  \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\nCould we have a config to disable this rather costly new feature,\ntoo?\n\nAlso the first and the third level configuration names (the <slot>\nis at the third level) used by the core-git do not use dashed-words\nformat.  Please adhere to the current convention.\n\n> diff --git a/diff.c b/diff.c\n> index 534c12e..d37cb4f 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,11 @@ 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 *duplicates_added;\n> +static struct hashmap *duplicates_removed;\n> +static int hash_previous_line_added;\n> +static int hash_previous_line_removed;\n\nI think these should be added as new fields to diff_options\nstructure.\n"},{"id":"301157","messageId":"CA+P7+xqx4PHHoKT_PK5s5eOtZMG9QJTSHED_=+BHZ=U330AQtw@mail.gmail.com","threadId":"44002","inReplyTo":"xmqq1t0yqinr.fsf@gitster.mtv.corp.google.com","subject":"Re: [WIP PATCH v2] diff.c: emit moved lines with a different color","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2016-09-06T01:09:15Z","receivedAt":"2016-09-06T01:09:41Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Mon, Sep 5, 2016 at 11:57 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Stefan Beller <stefanbeller@gmail.com> writes:\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> Could we have a config to disable this rather costly new feature,\n> too?\n\nThat seems entirely reasonable, though we *do* have a configuration\nfor disabling color altogether.. is there any numbers on how much more\nthis costs to compute?\n\n>> +static struct hashmap *duplicates_added;\n>> +static struct hashmap *duplicates_removed;\n>> +static int hash_previous_line_added;\n>> +static int hash_previous_line_removed;\n>\n> I think these should be added as new fields to diff_options\n> structure.\n\nAgreed, those seem like good choices for diff_options.\n\nThanks,\nJake\n"},{"id":"301159","messageId":"CAGZ79kaCtYYSv-Wnz6-Xz6Mt1TwstO-GMBYWyhbO7tM9g5gumA@mail.gmail.com","threadId":"44002","inReplyTo":"xmqq1t0yqinr.fsf@gitster.mtv.corp.google.com","subject":"Re: [WIP PATCH v2] diff.c: emit moved lines with a different color","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-09-06T02:07:32Z","receivedAt":"2016-09-06T02:08:06Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Sep 5, 2016 at 11:57 AM, Junio C Hamano <gitster@pobox.com> wrote:\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> Could we have a config to disable this rather costly new feature,\n> too?\n\nAnd by config option you mean both a command line parameter\n`--color=yes-but-no-move-detection` as well as a diff.color config option?\n\nAs it is currently `--color=<when>` with when={always, never,auto},\nI don't think we want to add it as another parameter there, so maybe\n--color-type=<style> with style={minimal, full} whereas the minimal/full\ndescribes the amount of work needed. Though I think that is bad as there\nmight be other orthogonal features to this.\n\nSo maybe just a `--[no-]color-moved` ?\n\nAs a config option we'd go with color.moved=<bool> for now?\n\nI imagine we may want to refine the moved detection algorithm in the\nfuture, e.g. moved just in the patch, or moved from elsewhere in the\nrepo or whether the moved detection takes permutations into account\netc, so actually we'd want to have color.moved={none, this-patch} for\nnow. The command line parameter --color-moved=<style> would be the\nsame.\n\n>\n> Also the first and the third level configuration names (the <slot>\n> is at the third level) used by the core-git do not use dashed-words\n> format.  Please adhere to the current convention.\n\nwill do.\n\n>\n>> diff --git a/diff.c b/diff.c\n>> index 534c12e..d37cb4f 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,11 @@ 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 *duplicates_added;\n>> +static struct hashmap *duplicates_removed;\n>> +static int hash_previous_line_added;\n>> +static int hash_previous_line_removed;\n>\n> I think these should be added as new fields to diff_options\n> structure.\n\nMakes sense.\n"},{"id":"301160","messageId":"CAGZ79kYPtvJ7iF8G5ihUCa5NwvDFa_Rzh+N7ar9QA2x74p2Z9g@mail.gmail.com","threadId":"44002","inReplyTo":"CA+P7+xqx4PHHoKT_PK5s5eOtZMG9QJTSHED_=+BHZ=U330AQtw@mail.gmail.com","subject":"Re: [WIP PATCH v2] diff.c: emit moved lines with a different color","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-09-06T02:09:30Z","receivedAt":"2016-09-06T02:09:36Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Sep 5, 2016 at 6:09 PM, Jacob Keller <jacob.keller@gmail.com> wrote:\n> On Mon, Sep 5, 2016 at 11:57 AM, Junio C Hamano <gitster@pobox.com> wrote:\n>> Stefan Beller <stefanbeller@gmail.com> writes:\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>> Could we have a config to disable this rather costly new feature,\n>> too?\n>\n> That seems entirely reasonable, though we *do* have a configuration\n> for disabling color altogether.. is there any numbers on how much more\n> this costs to compute?\n\nThis new coloring is linear to the size of the patch, i.e. O(number of\nadded/removed lines) in memory and for computational efforts I'd\nthink it is O(n log n) as inserting into the hashmap is an amortized\nlog n.\n\n>\n>>> +static struct hashmap *duplicates_added;\n>>> +static struct hashmap *duplicates_removed;\n>>> +static int hash_previous_line_added;\n>>> +static int hash_previous_line_removed;\n>>\n>> I think these should be added as new fields to diff_options\n>> structure.\n>\n> Agreed, those seem like good choices for diff_options.\n\nyup.\n"},{"id":"301185","messageId":"xmqqoa41p59i.fsf@gitster.mtv.corp.google.com","threadId":"44002","inReplyTo":"CAGZ79kYPtvJ7iF8G5ihUCa5NwvDFa_Rzh+N7ar9QA2x74p2Z9g@mail.gmail.com","subject":"Re: [WIP PATCH v2] diff.c: emit moved lines with a different color","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-09-06T12:44:09Z","receivedAt":"2016-09-06T12:44:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> This new coloring is linear to the size of the patch, i.e. O(number of\n> added/removed lines) in memory and for computational efforts I'd\n> think it is O(n log n) as inserting into the hashmap is an amortized\n> log n.\n\nIn addition to that O(n log n) overhead for book-keeping, you are\ndoing at least twice the amount of work compared to the original, if\nyou are still running the same xdiff twice to implement the two pass\napproach.  That is why I thought this \"twice as slow, at least\"\nneeds to be off by default at least in the beginning.\n\nAlso there is the additional memory pressure coming from the fact\nthat the first pass will need to keep all the removed and added\nlines in-core for all filepairs.  If you keep the entire diff output\nin-core from the first pass, I do not think it would be that much\nmore memory overhead compared to what you are already doing, so the\ncost of running the same xdiff twice is relatively easy to reduce, I\nwould imagine?  Instead of running the second xdi_diff_outf(), you\ncan drive your callback function out of what has been queued in the\nfirst pass yourself.  But that is the next step \"optimization\" once\nwe got the basics right.\n\nBy the way, not running xdiff twice would also remove another worry\nI have about correctness, in that the approach depends on xdiff\nmachinery to produce byte-for-byte identical result given the same\npair of input.  The output may currently be reproducible, but that\nis an unnecessary and an expensive thing to rely on.\n\nYou may be able to save tons of memory if you do not store the line\ncontents duplicated.  The first pass callback can tell the line\nnumbers in preimage and postimage [*1*], so your record for a\nremoved line could be a pair <struct diff_filespec *, long lineno>\nwith whatever hash value you need to throw it into the hash bucket.\n\nI know we use a hash function and a line comparison function that\nare aware of -b/-w comparison in xdiff machinery, but I didn't see\nyou use them in your hashtable.  Can you match moved lines when\noperating under various whitespace-change-ignoring modes?\n\nThanks.\n\n\n[Footnote]\n\n*1* You can learn all sort of things from emit_callback structure;\n    if you need to pass more data from the caller of xdi_diff_outf()\n    to the callback, you can even add new fields to it.\n\n"},{"id":"301210","messageId":"CAGZ79kZXbWUg8vQaPWCxjf=hfRH3k=cZwvC3o_D9gN4WmnyhUA@mail.gmail.com","threadId":"44002","inReplyTo":"xmqqoa41p59i.fsf@gitster.mtv.corp.google.com","subject":"Re: [WIP PATCH v2] diff.c: emit moved lines with a different color","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-09-06T16:47:53Z","receivedAt":"2016-09-06T16:48:02Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Sep 6, 2016 at 5:44 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> By the way, not running xdiff twice would also remove another worry\n> I have about correctness, in that the approach depends on xdiff\n> machinery to produce byte-for-byte identical result given the same\n> pair of input.\n\nAs we use different parameters to the xdiff machinery (e.g. context = 1 line)\nthe output is not  byte-for-byte identical.\n\n> The output may currently be reproducible, but that\n> is an unnecessary and an expensive thing to rely on.\n\nMy original design was to not store the lines in the hashmap but\nonly pointers to them, such that the additional memory pressure was\nassumed less than storing the whole output of the xdiff machinery.\n\nThat point is moot though in the current implementation, so it\nwould be better indeed if we run the xdiff machinery once and store\nall its output and then operate on that, even from a memory perspective.\n\n>\n> You may be able to save tons of memory if you do not store the line\n> contents duplicated.  The first pass callback can tell the line\n> numbers in preimage and postimage [*1*], so your record for a\n> removed line could be a pair <struct diff_filespec *, long lineno>\n> with whatever hash value you need to throw it into the hash bucket.\n\nYeah I guess I'll go that way in the next patch then.\n\n>\n> I know we use a hash function and a line comparison function that\n> are aware of -b/-w comparison in xdiff machinery, but I didn't see\n> you use them in your hashtable.  Can you match moved lines when\n> operating under various whitespace-change-ignoring modes?\n\nNot yet.\n\nThanks,\nStefan\n\n>\n> Thanks.\n>\n>\n> [Footnote]\n>\n> *1* You can learn all sort of things from emit_callback structure;\n>     if you need to pass more data from the caller of xdi_diff_outf()\n>     to the callback, you can even add new fields to it.\n>\n"}]}