{"thread":{"id":"40713","subject":"[PATCH 1/4] diff-highlight: add `less -r` to cmd in README","startedAt":"2015-11-03T02:05:30Z","lastAt":"2015-11-17T22:50:45Z","messageCount":17,"participants":["Jonathan Lebon","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"272778","messageId":"1446516334-27652-1-git-send-email-jonathan.lebon@gmail.com","threadId":"40713","inReplyTo":null,"subject":"[PATCH 0/4] diff-highlight: make a few improvements","fromName":"Jonathan Lebon","fromEmail":"jonathan.lebon@gmail.com","sentAt":"2015-11-03T02:05:30Z","receivedAt":"2015-11-03T02:05:30Z","isPatch":true,"sender":{"key":"jonathan.lebon@gmail.com","avatar":null},"body":"These patches bring a few improvements to the contrib/diff-highlight\nPerl script. The major improvement is done in patch 3/4, which improves\ndiff-highlighting accuracy by implementing a recursive line matching\nalgorithm.\n\nPlease note that I have limited experience with Perl, so there may be\nbetter ways to do things. (Let me know if that is the case!)\n\nJonathan Lebon (4):\n diff-highlight: add `less -r` to cmd in README\n diff-highlight: factor out prefix/suffix functions\n diff-highlight: match up lines before highlighting\n diff-highlight: add maxhunksize config option\n\n contrib/diff-highlight/README | 87 +++++-----------\n contrib/diff-highlight/diff-highlight | 189 ++++++++++++++++++++++++----------\n 2 files changed, 161 insertions(+), 115 deletions(-)\n\n-- \n2.6.0\n"},{"id":"272777","messageId":"1446516334-27652-2-git-send-email-jonathan.lebon@gmail.com","threadId":"40713","inReplyTo":"1446516334-27652-1-git-send-email-jonathan.lebon@gmail.com","subject":"[PATCH 1/4] diff-highlight: add `less -r` to cmd in README","fromName":"Jonathan Lebon","fromEmail":"jonathan.lebon@gmail.com","sentAt":"2015-11-03T02:05:31Z","receivedAt":"2015-11-03T02:05:31Z","isPatch":true,"sender":{"key":"jonathan.lebon@gmail.com","avatar":null},"body":"As it is, the suggested command for trying out diff-highlight will just\ndump the whole git log output to the terminal. Let's pipe it through\n`less` so users aren't surprised on the first try.\n\nSigned-off-by: Jonathan Lebon \n---\n contrib/diff-highlight/README | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/contrib/diff-highlight/README b/contrib/diff-highlight/README\nindex 836b97a..bbbfdda 100644\n--- a/contrib/diff-highlight/README\n+++ b/contrib/diff-highlight/README\n@@ -44,9 +44,9 @@ Use\n \n You can try out the diff-highlight program with:\n \n----------------------------------------------\n-git log -p --color | /path/to/diff-highlight\n----------------------------------------------\n+------------------------------------------------------\n+git log -p --color | /path/to/diff-highlight | less -r\n+------------------------------------------------------\n \n If you want to use it all the time, drop it in your $PATH and put the\n following in your git configuration:\n-- \n2.6.0\n"},{"id":"272780","messageId":"1446516334-27652-3-git-send-email-jonathan.lebon@gmail.com","threadId":"40713","inReplyTo":"1446516334-27652-1-git-send-email-jonathan.lebon@gmail.com","subject":"[PATCH 2/4] diff-highlight: factor out prefix/suffix functions","fromName":"Jonathan Lebon","fromEmail":"jonathan.lebon@gmail.com","sentAt":"2015-11-03T02:05:32Z","receivedAt":"2015-11-03T02:05:32Z","isPatch":true,"sender":{"key":"jonathan.lebon@gmail.com","avatar":null},"body":"In preparation for the next patch, we factor out the functions for\nfinding the common prefix and suffix between two lines.\n\nSigned-off-by: Jonathan Lebon \n---\n contrib/diff-highlight/diff-highlight | 98 ++++++++++++++++++++---------------\n 1 file changed, 56 insertions(+), 42 deletions(-)\n\ndiff --git a/contrib/diff-highlight/diff-highlight b/contrib/diff-highlight/diff-highlight\nindex ffefc31..a332f86 100755\n--- a/contrib/diff-highlight/diff-highlight\n+++ b/contrib/diff-highlight/diff-highlight\n@@ -110,48 +110,8 @@ sub highlight_pair {\n \tmy @a = split_line(shift);\n \tmy @b = split_line(shift);\n \n-\t# Find common prefix, taking care to skip any ansi\n-\t# color codes.\n-\tmy $seen_plusminus;\n-\tmy ($pa, $pb) = (0, 0);\n-\twhile ($pa < @a && $pb < @b) {\n-\t\tif ($a[$pa] =~ /$COLOR/) {\n-\t\t\t$pa++;\n-\t\t}\n-\t\telsif ($b[$pb] =~ /$COLOR/) {\n-\t\t\t$pb++;\n-\t\t}\n-\t\telsif ($a[$pa] eq $b[$pb]) {\n-\t\t\t$pa++;\n-\t\t\t$pb++;\n-\t\t}\n-\t\telsif (!$seen_plusminus && $a[$pa] eq '-' && $b[$pb] eq '+') {\n-\t\t\t$seen_plusminus = 1;\n-\t\t\t$pa++;\n-\t\t\t$pb++;\n-\t\t}\n-\t\telse {\n-\t\t\tlast;\n-\t\t}\n-\t}\n-\n-\t# Find common suffix, ignoring colors.\n-\tmy ($sa, $sb) = ($#a, $#b);\n-\twhile ($sa >= $pa && $sb >= $pb) {\n-\t\tif ($a[$sa] =~ /$COLOR/) {\n-\t\t\t$sa--;\n-\t\t}\n-\t\telsif ($b[$sb] =~ /$COLOR/) {\n-\t\t\t$sb--;\n-\t\t}\n-\t\telsif ($a[$sa] eq $b[$sb]) {\n-\t\t\t$sa--;\n-\t\t\t$sb--;\n-\t\t}\n-\t\telse {\n-\t\t\tlast;\n-\t\t}\n-\t}\n+\tmy ($pa, $pb) = find_common_prefix(\\@a, \\@b);\n+\tmy ($sa, $sb) = find_common_suffix(\\@a, $pa, \\@b, $pb);\n \n \tif (is_pair_interesting(\\@a, $pa, $sa, \\@b, $pb, $sb)) {\n \t\treturn highlight_line(\\@a, $pa, $sa, \\@OLD_HIGHLIGHT),\n@@ -173,6 +133,60 @@ sub split_line {\n \t\tsplit /($COLOR+)/;\n }\n \n+sub find_common_prefix {\n+\tmy ($a, $b) = @_;\n+\n+\t# Take care to skip any ansi color codes.\n+\tmy $seen_plusminus;\n+\tmy ($pa, $pb) = (0, 0);\n+\twhile ($pa < @$a && $pb < @$b) {\n+\t\tif ($a->[$pa] =~ /$COLOR/) {\n+\t\t\t$pa++;\n+\t\t}\n+\t\telsif ($b->[$pb] =~ /$COLOR/) {\n+\t\t\t$pb++;\n+\t\t}\n+\t\telsif ($a->[$pa] eq $b->[$pb]) {\n+\t\t\t$pa++;\n+\t\t\t$pb++;\n+\t\t}\n+\t\telsif (!$seen_plusminus && $a->[$pa] eq '-' && $b->[$pb] eq '+') {\n+\t\t\t$seen_plusminus = 1;\n+\t\t\t$pa++;\n+\t\t\t$pb++;\n+\t\t}\n+\t\telse {\n+\t\t\tlast;\n+\t\t}\n+\t}\n+\n+\treturn $pa, $pb;\n+}\n+\n+sub find_common_suffix {\n+\tmy ($a, $pa, $b, $pb) = @_;\n+\n+\t# Take care to skip any ansi color codes.\n+\tmy ($sa, $sb) = ($#$a, $#$b);\n+\twhile ($sa >= $pa && $sb >= $pb) {\n+\t\tif ($a->[$sa] =~ /$COLOR/) {\n+\t\t\t$sa--;\n+\t\t}\n+\t\telsif ($b->[$sb] =~ /$COLOR/) {\n+\t\t\t$sb--;\n+\t\t}\n+\t\telsif ($a->[$sa] eq $b->[$sb]) {\n+\t\t\t$sa--;\n+\t\t\t$sb--;\n+\t\t}\n+\t\telse {\n+\t\t\tlast;\n+\t\t}\n+\t}\n+\n+\treturn $sa, $sb;\n+}\n+\n sub highlight_line {\n \tmy ($line, $prefix, $suffix, $theme) = @_;\n \n-- \n2.6.0\n"},{"id":"272781","messageId":"1446516334-27652-4-git-send-email-jonathan.lebon@gmail.com","threadId":"40713","inReplyTo":"1446516334-27652-1-git-send-email-jonathan.lebon@gmail.com","subject":"[PATCH 3/4] diff-highlight: match up lines before highlighting","fromName":"Jonathan Lebon","fromEmail":"jonathan.lebon@gmail.com","sentAt":"2015-11-03T02:05:33Z","receivedAt":"2015-11-03T02:05:33Z","isPatch":true,"sender":{"key":"jonathan.lebon@gmail.com","avatar":null},"body":"As mentioned in the README, one of the current limitations of\ndiff-highlight is that it only calculates highlights when the hunk\ncontains the same number of removed lines as added lines.\n\nA further limitation upon this is that diff-highlight assumes that the\nfirst line removed matches the first line added, similarly with the\nsecond, the third, etc... As was demonstrated in the \"Bugs\" section of\nthe README, this poses limitations since that assumption does not always\ngive the best result.\n\nWith this patch, we eliminate those limitations by trying to match up\nthe removed and added lines before highlighting them. This is done using\na recursive algorithm.\n\nNote that I did not bother with some common optimizations such as\nmemoization since the usual number of removed/added lines in a single\nhunk are small. In practice, I have not felt any lag at all during\npaging.\n\nSigned-off-by: Jonathan Lebon \n---\n contrib/diff-highlight/README | 61 +------------------------\n contrib/diff-highlight/diff-highlight | 83 +++++++++++++++++++++++++++++------\n 2 files changed, 70 insertions(+), 74 deletions(-)\n\ndiff --git a/contrib/diff-highlight/README b/contrib/diff-highlight/README\nindex bbbfdda..885ff2f 100644\n--- a/contrib/diff-highlight/README\n+++ b/contrib/diff-highlight/README\n@@ -14,17 +14,7 @@ Instead, this script post-processes the line-oriented diff, finds pairs\n of lines, and highlights the differing segments. It's currently very\n simple and stupid about doing these tasks. In particular:\n \n- 1. It will only highlight hunks in which the number of removed and\n- added lines is the same, and it will pair lines within the hunk by\n- position (so the first removed line is compared to the first added\n- line, and so forth). This is simple and tends to work well in\n- practice. More complex changes don't highlight well, so we tend to\n- exclude them due to the \"same number of removed and added lines\"\n- restriction. Or even if we do try to highlight them, they end up\n- not highlighting because of our \"don't highlight if the whole line\n- would be highlighted\" rule.\n-\n- 2. It will find the common prefix and suffix of two lines, and\n+ 1. It will find the common prefix and suffix of two lines, and\n consider everything in the middle to be \"different\". It could\n instead do a real diff of the characters between the two lines and\n find common subsequences. However, the point of the highlight is to\n@@ -142,52 +132,3 @@ heuristics.\n -----------------------------------------------------\n \n which is less readable than the current output.\n-\n-2. The multi-line matching assumes that lines in the pre- and post-image\n- match by position. This is often the case, but can be fooled when a\n- line is removed from the top and a new one added at the bottom (or\n- vice versa). Unless the lines in the middle are also changed, diffs\n- will show this as two hunks, and it will not get highlighted at all\n- (which is good). But if the lines in the middle are changed, the\n- highlighting can be misleading. Here's a pathological case:\n-\n------------------------------------------------------\n--one\n--two\n--three\n--four\n-+two 2\n-+three 3\n-+four 4\n-+five 5\n------------------------------------------------------\n-\n- which gets highlighted as:\n-\n------------------------------------------------------\n--one\n--t-{wo}\n--three\n--f-{our}\n-+two 2\n-+t+{hree 3}\n-+four 4\n-+f+{ive 5}\n------------------------------------------------------\n-\n- because it matches \"two\" to \"three 3\", and so forth. It would be\n- nicer as:\n-\n------------------------------------------------------\n--one\n--two\n--three\n--four\n-+two +{2}\n-+three +{3}\n-+four +{4}\n-+five 5\n------------------------------------------------------\n-\n- which would probably involve pre-matching the lines into pairs\n- according to some heuristic.\ndiff --git a/contrib/diff-highlight/diff-highlight b/contrib/diff-highlight/diff-highlight\nindex a332f86..46556fc 100755\n--- a/contrib/diff-highlight/diff-highlight\n+++ b/contrib/diff-highlight/diff-highlight\n@@ -88,24 +88,79 @@ sub show_hunk {\n \t\treturn;\n \t}\n \n-\t# If we have mismatched numbers of lines on each side, we could try to\n-\t# be clever and match up similar lines. But for now we are simple and\n-\t# stupid, and only handle multi-line hunks that remove and add the same\n-\t# number of lines.\n-\tif (@$a != @$b) {\n-\t\tprint @$a, @$b;\n-\t\treturn;\n-\t}\n-\n \tmy @queue;\n-\tfor (my $i = 0; $i < @$a; $i++) {\n-\t\tmy ($rm, $add) = highlight_pair($a->[$i], $b->[$i]);\n-\t\tprint $rm;\n-\t\tpush @queue, $add;\n-\t}\n+\tmatch_and_highlight_pairs($a, 0, scalar @$a, $b, 0, scalar @$b, \\@queue);\n \tprint @queue;\n }\n \n+# Here, we try to be clever and match up similar lines. I.e. we try to\n+# find which lines in the `rem` lines (array a) became which other lines\n+# in the `add` lines (array b). To do this, we use a recursive algorithm\n+# that works as follow:\n+# \t1. Find the most similar pair of lines in all possible pairs\n+# \t2. Do a recursive call to find the most similar pair of lines in all\n+# \t pairs, restricted to lower indices\n+# \t3. Print the `rem` line of the best pair\n+# \t4. Queue the `add` line of the best pair\n+# \t5. Do a recursive call to find the most similar pair of lines in all\n+# \t pairs, restricted to higher indices\n+sub match_and_highlight_pairs {\n+\tmy ($a, $a_first, $a_last, $b, $b_first, $b_last, $queue) = @_;\n+\n+\t# base case: no more rem or add lines to pair up\n+\tif ($a_first >= $a_last || $b_first >= $b_last) {\n+\n+\t\t# flush out any remaining rem lines\n+\t\tfor (my $i = $a_first; $i < $a_last; $i++) {\n+\t\t\tprint $a->[$i];\n+\t\t}\n+\n+\t\t# queue up any remaining add lines\n+\t\tfor (my $i = $b_first; $i < $b_last; $i++) {\n+\t\t\tpush @$queue, $b->[$i];\n+\t\t}\n+\n+\t\treturn;\n+\t}\n+\n+\t# prime the loop\n+\tmy ($besti, $bestj) = ($a_first, $b_first);\n+\tmy $bestn = calculate_match($a->[$a_first], $b->[$b_first]) + 1;\n+\n+\tfor (my $i = $a_first; $i < $a_last; $i++) {\n+\t\tfor (my $j = $b_first; $j < $b_last; $j++) {\n+\t\t\tmy $n = calculate_match($a->[$i], $b->[$j]);\n+\t\t\tif ($n < $bestn) {\n+\t\t\t\t($besti, $bestj, $bestn) = ($i, $j, $n);\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t# find the best matches in the lower pairs\n+\tmatch_and_highlight_pairs($a, $a_first, $besti, $b, $b_first, $bestj, $queue);\n+\n+\tmy ($rm, $add) = highlight_pair($a->[$besti], $b->[$bestj]);\n+\tprint $rm;\n+\tpush @$queue, $add;\n+\n+\t# find the best matches in the higher pairs\n+\tmatch_and_highlight_pairs($a, $besti+1, $a_last, $b, $bestj+1, $b_last, $queue);\n+}\n+\n+# A measure of how well the two lines passed match up. The smaller the\n+# returned value, the better the match. The current implementation uses\n+# a simple heuristic which tries to minimize the overall diff between\n+# the two lines considering only their common prefix and suffix.\n+sub calculate_match {\n+\tmy @a = split_line(shift);\n+\tmy @b = split_line(shift);\n+\n+\tmy ($pa, $pb) = find_common_prefix(\\@a, \\@b);\n+\tmy ($sa, $sb) = find_common_suffix(\\@a, $pa, \\@b, $pb);\n+\n+\treturn ($sa - $pa) + ($sb - $pb);\n+}\n+\n sub highlight_pair {\n \tmy @a = split_line(shift);\n \tmy @b = split_line(shift);\n-- \n2.6.0\n"},{"id":"272779","messageId":"1446516334-27652-5-git-send-email-jonathan.lebon@gmail.com","threadId":"40713","inReplyTo":"1446516334-27652-1-git-send-email-jonathan.lebon@gmail.com","subject":"[PATCH 4/4] diff-highlight: add maxhunksize config option","fromName":"Jonathan Lebon","fromEmail":"jonathan.lebon@gmail.com","sentAt":"2015-11-03T02:05:34Z","receivedAt":"2015-11-03T02:05:34Z","isPatch":true,"sender":{"key":"jonathan.lebon@gmail.com","avatar":null},"body":"As the size of the hunk gets bigger, it becomes harder to jump back and\nforth between the removed and added lines, and highlighting becomes less\nbeneficial. We add a new config option called\n\n\tdiff-highlight.maxhunksize\n\nwhich controls the maximum size of the hunk allowed for which\nhighlighting is still performed. The default value is set to 20.\n\nSigned-off-by: Jonathan Lebon \n---\n contrib/diff-highlight/README | 20 ++++++++++++++++++++\n contrib/diff-highlight/diff-highlight | 16 ++++++++++++++++\n 2 files changed, 36 insertions(+)\n\ndiff --git a/contrib/diff-highlight/README b/contrib/diff-highlight/README\nindex 885ff2f..ed12be1 100644\n--- a/contrib/diff-highlight/README\n+++ b/contrib/diff-highlight/README\n@@ -89,6 +89,26 @@ newHighlight = \"black #aaffaa\"\n ---------------------------------------------\n \n \n+Max Hunk Config\n+---------------\n+\n+By default, diff-highlight will not do any highlighting if either the\n+number of removed or added lines is greater than 20. This is because as\n+the hunk gets bigger, it becomes harder to jump back and forth between\n+the removed and added lines, and highlighting becomes less beneficial.\n+\n+You can change this default by setting the \"diff-highlight.maxhunksize\"\n+configuration.\n+\n+Example:\n+\n+---------------------------------------------\n+# Increase the maximum diff-highlight to 30\n+[diff-highlight]\n+maxhunksize = 30\n+---------------------------------------------\n+\n+\n Bugs\n ----\n \ndiff --git a/contrib/diff-highlight/diff-highlight b/contrib/diff-highlight/diff-highlight\nindex 46556fc..a005146 100755\n--- a/contrib/diff-highlight/diff-highlight\n+++ b/contrib/diff-highlight/diff-highlight\n@@ -17,6 +17,8 @@ my @NEW_HIGHLIGHT = (\n \tcolor_config('color.diff-highlight.newreset', $OLD_HIGHLIGHT[2])\n );\n \n+my $MAX_HUNK_SIZE = config('diff-highlight.maxhunksize', 20);\n+\n my $RESET = \"\\x1b[m\";\n my $COLOR = qr/\\x1b\\[[0-9;]*m/;\n my $BORING = qr/$COLOR|\\s/;\n@@ -79,6 +81,13 @@ sub color_config {\n \treturn length($s) ? $s : $default;\n }\n \n+# Also handle our own fallback here to be independent.\n+sub config {\n+\tmy ($key, $default) = @_;\n+\tmy $s = `git config --get $key 2>/dev/null`;\n+\treturn length($s) ? $s : $default;\n+}\n+\n sub show_hunk {\n \tmy ($a, $b) = @_;\n \n@@ -88,6 +97,13 @@ sub show_hunk {\n \t\treturn;\n \t}\n \n+\t# Skip highlighting if the hunk gets bigger than the user configured\n+\t# limit.\n+\tif (@$a > $MAX_HUNK_SIZE || @$b > $MAX_HUNK_SIZE) {\n+\t\tprint @$a, @$b;\n+\t\treturn;\n+\t}\n+\n \tmy @queue;\n \tmatch_and_highlight_pairs($a, 0, scalar @$a, $b, 0, scalar @$b, \\@queue);\n \tprint @queue;\n-- \n2.6.0\n"},{"id":"272782","messageId":"xmqq7flzerda.fsf@gitster.mtv.corp.google.com","threadId":"40713","inReplyTo":"1446516334-27652-2-git-send-email-jonathan.lebon@gmail.com","subject":"Re: [PATCH 1/4] diff-highlight: add `less -r` to cmd in README","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-11-03T02:41:53Z","receivedAt":"2015-11-03T02:41:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Lebon writes:\n\n> As it is, the suggested command for trying out diff-highlight will just\n> dump the whole git log output to the terminal. Let's pipe it through\n> `less` so users aren't surprised on the first try.\n\nThat justifies the \"less\" part but not your choice of \"-r\".\n\nI am assuming that you are telling \"less\" not to show the ANSI\n\"color\" escape sequences using the caret notation with \"-r\", which\nis a very natural and sensible thing to do when using `highlight`.\n\nBut if that is the case, you don't want \"-r\" (raw control chars for\neverything). You would want to say \"-R\", I think.\n\nOther than that, looks like a sensible thing to do to me.\n\nThanks.\n\n\n> Signed-off-by: Jonathan Lebon \n> ---\n> contrib/diff-highlight/README | 6 +++---\n> 1 file changed, 3 insertions(+), 3 deletions(-)\n>\n> diff --git a/contrib/diff-highlight/README b/contrib/diff-highlight/README\n> index 836b97a..bbbfdda 100644\n> --- a/contrib/diff-highlight/README\n> +++ b/contrib/diff-highlight/README\n> @@ -44,9 +44,9 @@ Use\n> \n> You can try out the diff-highlight program with:\n> \n> ----------------------------------------------\n> -git log -p --color | /path/to/diff-highlight\n> ----------------------------------------------\n> +------------------------------------------------------\n> +git log -p --color | /path/to/diff-highlight | less -r\n> +------------------------------------------------------\n> \n> If you want to use it all the time, drop it in your $PATH and put the\n> following in your git configuration:\n"},{"id":"272783","messageId":"CAM0PgJ6XZmtuSXPq77V_TSoj_b=KhU2AFxmUgbkoE_f9e8Prmw@mail.gmail.com","threadId":"40713","inReplyTo":"xmqq7flzerda.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/4] diff-highlight: add `less -r` to cmd in README","fromName":"Jonathan Lebon","fromEmail":"jonathan.lebon@gmail.com","sentAt":"2015-11-03T03:12:13Z","receivedAt":"2015-11-03T03:12:13Z","isPatch":true,"sender":{"key":"jonathan.lebon@gmail.com","avatar":null},"body":"On Mon, Nov 2, 2015 at 9:41 PM, Junio C Hamano wrote:\n>\n> Jonathan Lebon writes:\n>\n> > As it is, the suggested command for trying out diff-highlight will just\n> > dump the whole git log output to the terminal. Let's pipe it through\n> > `less` so users aren't surprised on the first try.\n>\n> That justifies the \"less\" part but not your choice of \"-r\".\n>\n> I am assuming that you are telling \"less\" not to show the ANSI\n> \"color\" escape sequences using the caret notation with \"-r\", which\n> is a very natural and sensible thing to do when using `highlight`.\n>\n> But if that is the case, you don't want \"-r\" (raw control chars for\n> everything). You would want to say \"-R\", I think.\n\nAhh thanks, that makes sense. I will update this for v2 tomorrow.\n"},{"id":"272853","messageId":"20151103211435.GA22484@sigill.intra.peff.net","threadId":"40713","inReplyTo":"1446516334-27652-2-git-send-email-jonathan.lebon@gmail.com","subject":"Re: [PATCH 1/4] diff-highlight: add `less -r` to cmd in README","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-03T21:14:36Z","receivedAt":"2015-11-03T21:14:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 02, 2015 at 09:05:31PM -0500, Jonathan Lebon wrote:\n\n> As it is, the suggested command for trying out diff-highlight will just\n> dump the whole git log output to the terminal. Let's pipe it through\n> `less` so users aren't surprised on the first try.\n\nThat makes sense. I use \"diff-highlight | less\" myself, of course. I\nthink I excluded it from the README in the name of simplicity, but you\nare right that it is probably better to give a complete working example.\n\nI agree with Junio that \"-R\" is a more sensible default, but I don't\nthink that should be necessary. We already set LESS when running the\npager (and if you are overriding it, you are already in trouble, because\ngit itself will generate ANSI codes by default).\n\n-Peff\n"},{"id":"272854","messageId":"20151103211716.GB22484@sigill.intra.peff.net","threadId":"40713","inReplyTo":"1446516334-27652-3-git-send-email-jonathan.lebon@gmail.com","subject":"Re: [PATCH 2/4] diff-highlight: factor out prefix/suffix functions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-03T21:17:16Z","receivedAt":"2015-11-03T21:17:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 02, 2015 at 09:05:32PM -0500, Jonathan Lebon wrote:\n\n> In preparation for the next patch, we factor out the functions for\n> finding the common prefix and suffix between two lines.\n\nLooks like a pretty straightforward movement. Your perl adjustments to\nuse array refs look good, and I think the multi-valued return is a good\ninterface.\n\n-Peff\n"},{"id":"272856","messageId":"20151103214416.GC22484@sigill.intra.peff.net","threadId":"40713","inReplyTo":"1446516334-27652-4-git-send-email-jonathan.lebon@gmail.com","subject":"Re: [PATCH 3/4] diff-highlight: match up lines before highlighting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-03T21:44:16Z","receivedAt":"2015-11-03T21:44:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 02, 2015 at 09:05:33PM -0500, Jonathan Lebon wrote:\n\n> As mentioned in the README, one of the current limitations of\n> diff-highlight is that it only calculates highlights when the hunk\n> contains the same number of removed lines as added lines.\n> \n> A further limitation upon this is that diff-highlight assumes that the\n> first line removed matches the first line added, similarly with the\n> second, the third, etc... As was demonstrated in the \"Bugs\" section of\n> the README, this poses limitations since that assumption does not always\n> give the best result.\n> \n> With this patch, we eliminate those limitations by trying to match up\n> the removed and added lines before highlighting them. This is done using\n> a recursive algorithm.\n\nHmm. So this seems like a reasonable incremental feature. I do think it\nis a hack (piled on the hack that is the existing script :) ), and the\nright solution is to actually do an LCS diff for each hunk that crosses\nline boundaries.\n\nI made some headway on that this summer as part of this discussion:\n\n http://thread.gmane.org/gmane.comp.version-control.git/271692\n\nIt's long, but there's some good stuff in there. But I think I came to\nthe conclusion that this really needs to go inside of diff.c itself\n(which will also require some heavy refactoring of the whitespace code;\nsee the referenced thread for details).\n\nBut I'm not opposed to an incremental feature like this in the meantime.\nThe real test for me is: how does it look in practice? These are all\nheuristics, so I don't think we have anything better than eyeballing the\noutput.\n\nHave you looked at a diff of the old/new output on something like\ngit.git?\n\n> Note that I did not bother with some common optimizations such as\n> memoization since the usual number of removed/added lines in a single\n> hunk are small. In practice, I have not felt any lag at all during\n> paging.\n\nI'd worry less about normal use, and more about hitting some extreme\ncorner case. Your algorithm looks roughly quadratic in the size of the\nhunk. I guess that is canceled out by the max-hunk-size option in the\nnext patch, though.\n\nI don't think it's easy to make your algorithm non-quadratic, either, as\nit inherently relies on pairwise comparisons (and not, say, generating a\nfingerprint of each line and sorting them or something like that).\n\nIt might be worth memo-izing find_common_* calls, though, as that is\njust repeated work (quadratic or not). It should be easy to time.\n\n> +\t# prime the loop\n> +\tmy ($besti, $bestj) = ($a_first, $b_first);\n> +\tmy $bestn = calculate_match($a->[$a_first], $b->[$b_first]) + 1;\n> +\n> +\tfor (my $i = $a_first; $i < $a_last; $i++) {\n> +\t\tfor (my $j = $b_first; $j < $b_last; $j++) {\n> +\t\t\tmy $n = calculate_match($a->[$i], $b->[$j]);\n> +\t\t\tif ($n < $bestn) {\n> +\t\t\t\t($besti, $bestj, $bestn) = ($i, $j, $n);\n> +\t\t\t}\n> +\t\t}\n> +\t}\n> +\n> +\t# find the best matches in the lower pairs\n> +\tmatch_and_highlight_pairs($a, $a_first, $besti, $b, $b_first, $bestj, $queue);\n\nHmm, is this actually O(n^3)? We have a quadratic loop, and then we\nrecurse for the remainder.\n\nIf we have two candidates for which calculate_match returns the same\nvalue, how do we break the tie? It looks like we'll just pick the\nlowest-numbered match. I'd think we would want to prefer the one with\nthe closest line number. But not having thought too hard about it, I\nwonder:\n\n 1. Does it actually make a difference which line we pick? The\n interesting bit is how much we highlight, so in that sense do we\n care only about the prefix and suffix sizes?\n\n 2. Do you end up picking the closest line with your algorithm anyway,\n as will tend to match as we go, skipping over only lines that will\n likely have no match?\n\n-Peff\n"},{"id":"272857","messageId":"20151103214600.GD22484@sigill.intra.peff.net","threadId":"40713","inReplyTo":"1446516334-27652-5-git-send-email-jonathan.lebon@gmail.com","subject":"Re: [PATCH 4/4] diff-highlight: add maxhunksize config option","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-03T21:46:00Z","receivedAt":"2015-11-03T21:46:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 02, 2015 at 09:05:34PM -0500, Jonathan Lebon wrote:\n\n> As the size of the hunk gets bigger, it becomes harder to jump back and\n> forth between the removed and added lines, and highlighting becomes less\n> beneficial. We add a new config option called\n> \n> \tdiff-highlight.maxhunksize\n> \n> which controls the maximum size of the hunk allowed for which\n> highlighting is still performed. The default value is set to 20.\n\nI think this makes sense. I'm pleased it is here to limit the problem\nspace for patch 3, but I think it has value on its own as a heuristic.\n\n-Peff\n"},{"id":"272858","messageId":"xmqqwptybvk5.fsf@gitster.mtv.corp.google.com","threadId":"40713","inReplyTo":"20151103211435.GA22484@sigill.intra.peff.net","subject":"Re: [PATCH 1/4] diff-highlight: add `less -r` to cmd in README","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-11-03T21:51:54Z","receivedAt":"2015-11-03T21:51:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I agree with Junio that \"-R\" is a more sensible default, but I don't\n> think that should be necessary. We already set LESS when running the\n> pager (and if you are overriding it, you are already in trouble, because\n> git itself will generate ANSI codes by default).\n\nI do not quite understand this part. Inside git itself when we\nspawn the pager we export LESS with a sensible default, exactly to\nhelp users who do not have LESS set and exported. This one however\nis not spawned by git but the end-user piping output of diff-hilite.\n\nI agree that if the user has LESS exported without -R that would not\nbe pretty while viewing coloured output.\n"},{"id":"272859","messageId":"20151103215535.GA24971@sigill.intra.peff.net","threadId":"40713","inReplyTo":"xmqqwptybvk5.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/4] diff-highlight: add `less -r` to cmd in README","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-03T21:55:35Z","receivedAt":"2015-11-03T21:55:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 03, 2015 at 01:51:54PM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > I agree with Junio that \"-R\" is a more sensible default, but I don't\n> > think that should be necessary. We already set LESS when running the\n> > pager (and if you are overriding it, you are already in trouble, because\n> > git itself will generate ANSI codes by default).\n> \n> I do not quite understand this part. Inside git itself when we\n> spawn the pager we export LESS with a sensible default, exactly to\n> help users who do not have LESS set and exported. This one however\n> is not spawned by git but the end-user piping output of diff-hilite.\n\nOh, you're right. I mistook it as instructions for what to put in\npager.log, but that is clearly not what this is. I agree that telling\nthe user to use \"-R\" here is a good idea.\n\nAnd indeed, the instructions just below the hunk in question describe\nsetting it properly in your config (with less, and no \"-R\"). So I was\nsimply confused and not reading carefully enough.\n\n-Peff\n"},{"id":"272860","messageId":"20151103220314.GE22484@sigill.intra.peff.net","threadId":"40713","inReplyTo":"20151103214416.GC22484@sigill.intra.peff.net","subject":"Re: [PATCH 3/4] diff-highlight: match up lines before highlighting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-03T22:03:14Z","receivedAt":"2015-11-03T22:03:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 03, 2015 at 04:44:16PM -0500, Jeff King wrote:\n\n> Have you looked at a diff of the old/new output on something like\n> git.git?\n\nThis should be pretty easy to do (and time). I tried:\n\n git log --oneline --color -p >base\n time perl highlight.old old\n time perl highlight.new new\n diff -c old new | less\n\nwhere the \"highlight.*\" scripts are the versions at master, and master\nwith your series applied.\n\nYour is _much_ slower. I get:\n\n real 0m25.538s\n user 0m25.420s\n sys 0m0.120s\n\nfor the old versus:\n\n real 2m3.580s\n user 2m3.548s\n sys 0m0.156s\n\nfor your series. In an interactive setting, the latency may not be that\nnoticeable, but if you are digging far into history (e.g., \"git log -p\",\nthen using \"/\" in less to search for a commit or some test), I suspect\nit would be very noticeable.\n\nI was thinking there was some low-hanging fruit in memoizing the\ncalculations, but even the prefix/suffix computation is pairwise. I'm\nnot really sure how to make this much faster.\n\nAs for the output itself, the diff between the two looks promising. The\nfirst several cases I looked at ar strict improvements. Some of them are\nkind of weird, especially in English text. For example, see the RelNotes\nupdate in 2635c2b. The base diff is:\n\n * \"git rebase -i\" had a minor regression recently, which stopped\n considering a line that begins with an indented '#' in its insn\n- sheet not a comment, which is now fixed.\n- (merge 1db168e gr/rebase-i-drop-warn later to maint).\n+ sheet not a comment. Further, the code was still too picky on\n+ Windows where CRLF left by the editor is turned into a trailing CR\n+ on the line read via the \"read\" built-in command of bash. Both of\n+ these issues are now fixed.\n+ (merge 39743cf gr/rebase-i-drop-warn later to maint).\n\nBefore we highlighted nothing, and now we hone in on \"now fixed\". Which\nis _sort of_ a match, but really the whole sentence structure has\nchanged. If this is the worst regression, I can certainly live with it.\nAnd even a proper LCS diff would probably end up making spaghetti of a\ntext change like this.\n\nIn the other thread I mentioned earlier, the solution I cooked up was\ndropping highlighting entirely for hunks over a certain percentage of\nhighlighting. I wonder if we could do something similar here (e.g.,\ndon't match lines where more than 50% of the line would be highlighted).\n\n-Peff\n"},{"id":"272861","messageId":"20151103220723.GF22484@sigill.intra.peff.net","threadId":"40713","inReplyTo":"1446516334-27652-1-git-send-email-jonathan.lebon@gmail.com","subject":"Re: [PATCH 0/4] diff-highlight: make a few improvements","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-03T22:07:23Z","receivedAt":"2015-11-03T22:07:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 02, 2015 at 09:05:30PM -0500, Jonathan Lebon wrote:\n\n> These patches bring a few improvements to the contrib/diff-highlight\n> Perl script. The major improvement is done in patch 3/4, which improves\n> diff-highlighting accuracy by implementing a recursive line matching\n> algorithm.\n> \n> Please note that I have limited experience with Perl, so there may be\n> better ways to do things. (Let me know if that is the case!)\n\nI forgot to mention in the rest of my review: thank you for working on\nthis, and for making a nice clean series. It was very pleasant to read.\n\nI think the output overall is nicer. I am concerned with the performance\nimplications. I see this as a stopgap until we have a true diff inside\nthe hunks, but if we can overcome the performance implications, I think\nit's worth applying in the meantime.\n\n-Peff\n"},{"id":"273407","messageId":"CAM0PgJ4erahEZsL75c4mytF158xxeE6itG8KOMMi4n-zBTHcww@mail.gmail.com","threadId":"40713","inReplyTo":"20151103220314.GE22484@sigill.intra.peff.net","subject":"Re: [PATCH 3/4] diff-highlight: match up lines before highlighting","fromName":"Jonathan Lebon","fromEmail":"jonathan.lebon@gmail.com","sentAt":"2015-11-17T05:18:28Z","receivedAt":"2015-11-17T05:18:28Z","isPatch":true,"sender":{"key":"jonathan.lebon@gmail.com","avatar":null},"body":"On Tue, Nov 3, 2015 at 5:03 PM, Jeff King wrote:\n> Your is _much_ slower. I get:\n>\n> real 0m25.538s\n> user 0m25.420s\n> sys 0m0.120s\n>\n> for the old versus:\n>\n> real 2m3.580s\n> user 2m3.548s\n> sys 0m0.156s\n\nThanks for investigating and trying it out. I got the same results\nhere as well.\n\n> for your series. In an interactive setting, the latency may not be that\n> noticeable, but if you are digging far into history (e.g., \"git log -p\",\n> then using \"/\" in less to search for a commit or some test), I suspect\n> it would be very noticeable.\n\nAgreed.\n\n> I was thinking there was some low-hanging fruit in memoizing the\n> calculations, but even the prefix/suffix computation is pairwise. I'm\n> not really sure how to make this much faster.\n\nI gave memoization a try to see if it could improve the situation. I also\nlowered maxhunksize to 10. Doing `git log -p` on git.git went from 2m31\nto 2m11. So I think it would require a whole other approach overall.\n\n> As for the output itself, the diff between the two looks promising. The\n> first several cases I looked at ar strict improvements. Some of them are\n> kind of weird, especially in English text.\n\nYes, I'm very happy with the improvements and run with these patches all\nthe time for now.\n\n> In the other thread I mentioned earlier, the solution I cooked up was\n> dropping highlighting entirely for hunks over a certain percentage of\n> highlighting. I wonder if we could do something similar here (e.g.,\n> don't match lines where more than 50% of the line would be highlighted).\n\nI looked over but haven't tested the patches in the other thread yet. But\noverall, the LCS definitely looks promising. I'm hoping to find some time\nto have a more serious go at it and maybe pick it up where you left off.\n\n>\n> -Peff\n\nThanks again for reviewing these patches and apologies for the delayed\nreply.\n\nJonathan\n"},{"id":"273451","messageId":"20151117225045.GF27862@sigill.intra.peff.net","threadId":"40713","inReplyTo":"CAM0PgJ4erahEZsL75c4mytF158xxeE6itG8KOMMi4n-zBTHcww@mail.gmail.com","subject":"Re: [PATCH 3/4] diff-highlight: match up lines before highlighting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-17T22:50:45Z","receivedAt":"2015-11-17T22:50:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 17, 2015 at 12:18:28AM -0500, Jonathan Lebon wrote:\n\n> > In the other thread I mentioned earlier, the solution I cooked up was\n> > dropping highlighting entirely for hunks over a certain percentage of\n> > highlighting. I wonder if we could do something similar here (e.g.,\n> > don't match lines where more than 50% of the line would be highlighted).\n> \n> I looked over but haven't tested the patches in the other thread yet. But\n> overall, the LCS definitely looks promising. I'm hoping to find some time\n> to have a more serious go at it and maybe pick it up where you left off.\n> [...]\n> Thanks again for reviewing these patches and apologies for the delayed\n> reply.\n\nGreat! I look forward to seeing what you produce. Let me know if you\nwant me to clarify anything from that earlier discussion.\n\nAnd don't worry about delayed replies; it's part of the normal workflow\naround here.\n\n-Peff\n"}]}