6 files changed, 743 insertions, 0 deletions
diff --git a/contrib/diff-highlight/Makefile b/contrib/diff-highlight/Makefile
new file mode 100644
index 0000000000..9018724524
--- /dev/null
+++ b/contrib/diff-highlight/Makefile
@@ -0,0 +1,5 @@
+# nothing to build
+all:
+
+test:
+	$(MAKE) -C t
diff --git a/contrib/diff-highlight/README b/contrib/diff-highlight/README
new file mode 100644
index 0000000000..836b97a730
--- /dev/null
+++ b/contrib/diff-highlight/README
@@ -0,0 +1,193 @@
+diff-highlight
+==============
+
+Line oriented diffs are great for reviewing code, because for most
+hunks, you want to see the old and the new segments of code next to each
+other. Sometimes, though, when an old line and a new line are very
+similar, it's hard to immediately see the difference.
+
+You can use "--color-words" to highlight only the changed portions of
+lines. However, this can often be hard to read for code, as it loses
+the line structure, and you end up with oddly formatted bits.
+
+Instead, this script post-processes the line-oriented diff, finds pairs
+of lines, and highlights the differing segments.  It's currently very
+simple and stupid about doing these tasks. In particular:
+
+  1. It will only highlight hunks in which the number of removed and
+     added lines is the same, and it will pair lines within the hunk by
+     position (so the first removed line is compared to the first added
+     line, and so forth). This is simple and tends to work well in
+     practice. More complex changes don't highlight well, so we tend to
+     exclude them due to the "same number of removed and added lines"
+     restriction. Or even if we do try to highlight them, they end up
+     not highlighting because of our "don't highlight if the whole line
+     would be highlighted" rule.
+
+  2. It will find the common prefix and suffix of two lines, and
+     consider everything in the middle to be "different". It could
+     instead do a real diff of the characters between the two lines and
+     find common subsequences. However, the point of the highlight is to
+     call attention to a certain area. Even if some small subset of the
+     highlighted area actually didn't change, that's OK. In practice it
+     ends up being more readable to just have a single blob on the line
+     showing the interesting bit.
+
+The goal of the script is therefore not to be exact about highlighting
+changes, but to call attention to areas of interest without being
+visually distracting.  Non-diff lines and existing diff coloration is
+preserved; the intent is that the output should look exactly the same as
+the input, except for the occasional highlight.
+
+Use
+---
+
+You can try out the diff-highlight program with:
+
+---------------------------------------------
+git log -p --color | /path/to/diff-highlight
+---------------------------------------------
+
+If you want to use it all the time, drop it in your $PATH and put the
+following in your git configuration:
+
+---------------------------------------------
+[pager]
+	log = diff-highlight | less
+	show = diff-highlight | less
+	diff = diff-highlight | less
+---------------------------------------------
+
+
+Color Config
+------------
+
+You can configure the highlight colors and attributes using git's
+config. The colors for "old" and "new" lines can be specified
+independently. There are two "modes" of configuration:
+
+  1. You can specify a "highlight" color and a matching "reset" color.
+     This will retain any existing colors in the diff, and apply the
+     "highlight" and "reset" colors before and after the highlighted
+     portion.
+
+  2. You can specify a "normal" color and a "highlight" color. In this
+     case, existing colors are dropped from that line. The non-highlighted
+     bits of the line get the "normal" color, and the highlights get the
+     "highlight" color.
+
+If no "new" colors are specified, they default to the "old" colors. If
+no "old" colors are specified, the default is to reverse the foreground
+and background for highlighted portions.
+
+Examples:
+
+---------------------------------------------
+# Underline highlighted portions
+[color "diff-highlight"]
+oldHighlight = ul
+oldReset = noul
+---------------------------------------------
+
+---------------------------------------------
+# Varying background intensities
+[color "diff-highlight"]
+oldNormal = "black #f8cbcb"
+oldHighlight = "black #ffaaaa"
+newNormal = "black #cbeecb"
+newHighlight = "black #aaffaa"
+---------------------------------------------
+
+
+Bugs
+----
+
+Because diff-highlight relies on heuristics to guess which parts of
+changes are important, there are some cases where the highlighting is
+more distracting than useful. Fortunately, these cases are rare in
+practice, and when they do occur, the worst case is simply a little
+extra highlighting. This section documents some cases known to be
+sub-optimal, in case somebody feels like working on improving the
+heuristics.
+
+1. Two changes on the same line get highlighted in a blob. For example,
+   highlighting:
+
+----------------------------------------------
+-foo(buf, size);
++foo(obj->buf, obj->size);
+----------------------------------------------
+
+   yields (where the inside of "+{}" would be highlighted):
+
+----------------------------------------------
+-foo(buf, size);
++foo(+{obj->buf, obj->}size);
+----------------------------------------------
+
+   whereas a more semantically meaningful output would be:
+
+----------------------------------------------
+-foo(buf, size);
++foo(+{obj->}buf, +{obj->}size);
+----------------------------------------------
+
+   Note that doing this right would probably involve a set of
+   content-specific boundary patterns, similar to word-diff. Otherwise
+   you get junk like:
+
+-----------------------------------------------------
+-this line has some -{i}nt-{ere}sti-{ng} text on it
++this line has some +{fa}nt+{a}sti+{c} text on it
+-----------------------------------------------------
+
+   which is less readable than the current output.
+
+2. The multi-line matching assumes that lines in the pre- and post-image
+   match by position. This is often the case, but can be fooled when a
+   line is removed from the top and a new one added at the bottom (or
+   vice versa). Unless the lines in the middle are also changed, diffs
+   will show this as two hunks, and it will not get highlighted at all
+   (which is good). But if the lines in the middle are changed, the
+   highlighting can be misleading. Here's a pathological case:
+
+-----------------------------------------------------
+-one
+-two
+-three
+-four
++two 2
++three 3
++four 4
++five 5
+-----------------------------------------------------
+
+   which gets highlighted as:
+
+-----------------------------------------------------
+-one
+-t-{wo}
+-three
+-f-{our}
++two 2
++t+{hree 3}
++four 4
++f+{ive 5}
+-----------------------------------------------------
+
+   because it matches "two" to "three 3", and so forth. It would be
+   nicer as:
+
+-----------------------------------------------------
+-one
+-two
+-three
+-four
++two +{2}
++three +{3}
++four +{4}
++five 5
+-----------------------------------------------------
+
+   which would probably involve pre-matching the lines into pairs
+   according to some heuristic.
diff --git a/contrib/diff-highlight/diff-highlight b/contrib/diff-highlight/diff-highlight
new file mode 100755
index 0000000000..81bd8040e3
--- /dev/null
+++ b/contrib/diff-highlight/diff-highlight
@@ -0,0 +1,225 @@
+#!/usr/bin/perl
+
+use 5.008;
+use warnings FATAL => 'all';
+use strict;
+
+# Highlight by reversing foreground and background. You could do
+# other things like bold or underline if you prefer.
+my @OLD_HIGHLIGHT = (
+	color_config('color.diff-highlight.oldnormal'),
+	color_config('color.diff-highlight.oldhighlight', "\x1b[7m"),
+	color_config('color.diff-highlight.oldreset', "\x1b[27m")
+);
+my @NEW_HIGHLIGHT = (
+	color_config('color.diff-highlight.newnormal', $OLD_HIGHLIGHT[0]),
+	color_config('color.diff-highlight.newhighlight', $OLD_HIGHLIGHT[1]),
+	color_config('color.diff-highlight.newreset', $OLD_HIGHLIGHT[2])
+);
+
+my $RESET = "\x1b[m";
+my $COLOR = qr/\x1b\[[0-9;]*m/;
+my $BORING = qr/$COLOR|\s/;
+
+# The patch portion of git log -p --graph should only ever have preceding | and
+# not / or \ as merge history only shows up on the commit line.
+my $GRAPH = qr/$COLOR?\|$COLOR?\s+/;
+
+my @removed;
+my @added;
+my $in_hunk;
+
+# Some scripts may not realize that SIGPIPE is being ignored when launching the
+# pager--for instance scripts written in Python.
+$SIG{PIPE} = 'DEFAULT';
+
+while (<>) {
+	if (!$in_hunk) {
+		print;
+		$in_hunk = /^$GRAPH*$COLOR*\@\@ /;
+	}
+	elsif (/^$GRAPH*$COLOR*-/) {
+		push @removed, $_;
+	}
+	elsif (/^$GRAPH*$COLOR*\+/) {
+		push @added, $_;
+	}
+	else {
+		show_hunk(\@removed, \@added);
+		@removed = ();
+		@added = ();
+
+		print;
+		$in_hunk = /^$GRAPH*$COLOR*[\@ ]/;
+	}
+
+	# Most of the time there is enough output to keep things streaming,
+	# but for something like "git log -Sfoo", you can get one early
+	# commit and then many seconds of nothing. We want to show
+	# that one commit as soon as possible.
+	#
+	# Since we can receive arbitrary input, there's no optimal
+	# place to flush. Flushing on a blank line is a heuristic that
+	# happens to match git-log output.
+	if (!length) {
+		local $| = 1;
+	}
+}
+
+# Flush any queued hunk (this can happen when there is no trailing context in
+# the final diff of the input).
+show_hunk(\@removed, \@added);
+
+exit 0;
+
+# Ideally we would feed the default as a human-readable color to
+# git-config as the fallback value. But diff-highlight does
+# not otherwise depend on git at all, and there are reports
+# of it being used in other settings. Let's handle our own
+# fallback, which means we will work even if git can't be run.
+sub color_config {
+	my ($key, $default) = @_;
+	my $s = `git config --get-color $key 2>/dev/null`;
+	return length($s) ? $s : $default;
+}
+
+sub show_hunk {
+	my ($a, $b) = @_;
+
+	# If one side is empty, then there is nothing to compare or highlight.
+	if (!@$a || !@$b) {
+		print @$a, @$b;
+		return;
+	}
+
+	# If we have mismatched numbers of lines on each side, we could try to
+	# be clever and match up similar lines. But for now we are simple and
+	# stupid, and only handle multi-line hunks that remove and add the same
+	# number of lines.
+	if (@$a != @$b) {
+		print @$a, @$b;
+		return;
+	}
+
+	my @queue;
+	for (my $i = 0; $i < @$a; $i++) {
+		my ($rm, $add) = highlight_pair($a->[$i], $b->[$i]);
+		print $rm;
+		push @queue, $add;
+	}
+	print @queue;
+}
+
+sub highlight_pair {
+	my @a = split_line(shift);
+	my @b = split_line(shift);
+
+	# Find common prefix, taking care to skip any ansi
+	# color codes.
+	my $seen_plusminus;
+	my ($pa, $pb) = (0, 0);
+	while ($pa < @a && $pb < @b) {
+		if ($a[$pa] =~ /$COLOR/) {
+			$pa++;
+		}
+		elsif ($b[$pb] =~ /$COLOR/) {
+			$pb++;
+		}
+		elsif ($a[$pa] eq $b[$pb]) {
+			$pa++;
+			$pb++;
+		}
+		elsif (!$seen_plusminus && $a[$pa] eq '-' && $b[$pb] eq '+') {
+			$seen_plusminus = 1;
+			$pa++;
+			$pb++;
+		}
+		else {
+			last;
+		}
+	}
+
+	# Find common suffix, ignoring colors.
+	my ($sa, $sb) = ($#a, $#b);
+	while ($sa >= $pa && $sb >= $pb) {
+		if ($a[$sa] =~ /$COLOR/) {
+			$sa--;
+		}
+		elsif ($b[$sb] =~ /$COLOR/) {
+			$sb--;
+		}
+		elsif ($a[$sa] eq $b[$sb]) {
+			$sa--;
+			$sb--;
+		}
+		else {
+			last;
+		}
+	}
+
+	if (is_pair_interesting(\@a, $pa, $sa, \@b, $pb, $sb)) {
+		return highlight_line(\@a, $pa, $sa, \@OLD_HIGHLIGHT),
+		       highlight_line(\@b, $pb, $sb, \@NEW_HIGHLIGHT);
+	}
+	else {
+		return join('', @a),
+		       join('', @b);
+	}
+}
+
+# we split either by $COLOR or by character. This has the side effect of
+# leaving in graph cruft. It works because the graph cruft does not contain "-"
+# or "+"
+sub split_line {
+	local $_ = shift;
+	return utf8::decode($_) ?
+		map { utf8::encode($_); $_ }
+			map { /$COLOR/ ? $_ : (split //) }
+			split /($COLOR+)/ :
+		map { /$COLOR/ ? $_ : (split //) }
+		split /($COLOR+)/;
+}
+
+sub highlight_line {
+	my ($line, $prefix, $suffix, $theme) = @_;
+
+	my $start = join('', @{$line}[0..($prefix-1)]);
+	my $mid = join('', @{$line}[$prefix..$suffix]);
+	my $end = join('', @{$line}[($suffix+1)..$#$line]);
+
+	# If we have a "normal" color specified, then take over the whole line.
+	# Otherwise, we try to just manipulate the highlighted bits.
+	if (defined $theme->[0]) {
+		s/$COLOR//g for ($start, $mid, $end);
+		chomp $end;
+		return join('',
+			$theme->[0], $start, $RESET,
+			$theme->[1], $mid, $RESET,
+			$theme->[0], $end, $RESET,
+			"\n"
+		);
+	} else {
+		return join('',
+			$start,
+			$theme->[1], $mid, $theme->[2],
+			$end
+		);
+	}
+}
+
+# Pairs are interesting to highlight only if we are going to end up
+# highlighting a subset (i.e., not the whole line). Otherwise, the highlighting
+# is just useless noise. We can detect this by finding either a matching prefix
+# or suffix (disregarding boring bits like whitespace and colorization).
+sub is_pair_interesting {
+	my ($a, $pa, $sa, $b, $pb, $sb) = @_;
+	my $prefix_a = join('', @$a[0..($pa-1)]);
+	my $prefix_b = join('', @$b[0..($pb-1)]);
+	my $suffix_a = join('', @$a[($sa+1)..$#$a]);
+	my $suffix_b = join('', @$b[($sb+1)..$#$b]);
+
+	return $prefix_a !~ /^$GRAPH*$COLOR*-$BORING*$/ ||
+	       $prefix_b !~ /^$GRAPH*$COLOR*\+$BORING*$/ ||
+	       $suffix_a !~ /^$BORING*$/ ||
+	       $suffix_b !~ /^$BORING*$/;
+}
diff --git a/contrib/diff-highlight/t/.gitignore b/contrib/diff-highlight/t/.gitignore
new file mode 100644
index 0000000000..7dcbb232cd
--- /dev/null
+++ b/contrib/diff-highlight/t/.gitignore
@@ -0,0 +1,2 @@
+/trash directory*
+/test-results
diff --git a/contrib/diff-highlight/t/Makefile b/contrib/diff-highlight/t/Makefile
new file mode 100644
index 0000000000..5ff5275496
--- /dev/null
+++ b/contrib/diff-highlight/t/Makefile
@@ -0,0 +1,22 @@
+-include ../../../config.mak.autogen
+-include ../../../config.mak
+
+# copied from ../../t/Makefile
+SHELL_PATH ?= $(SHELL)
+SHELL_PATH_SQ = $(subst ','\'',$(SHELL_PATH))
+T = $(wildcard t[0-9][0-9][0-9][0-9]-*.sh)
+
+all: test
+test: $(T)
+
+.PHONY: help clean all test $(T)
+
+help:
+	@echo 'Run "$(MAKE) test" to launch test scripts'
+	@echo 'Run "$(MAKE) clean" to remove trash folders'
+
+$(T):
+	@echo "*** $@ ***"; '$(SHELL_PATH_SQ)' $@ $(GIT_TEST_OPTS)
+
+clean:
+	$(RM) -r 'trash directory'.*
diff --git a/contrib/diff-highlight/t/t9400-diff-highlight.sh b/contrib/diff-highlight/t/t9400-diff-highlight.sh
new file mode 100755
index 0000000000..3b43dbed74
--- /dev/null
+++ b/contrib/diff-highlight/t/t9400-diff-highlight.sh
@@ -0,0 +1,296 @@
+#!/bin/sh
+
+test_description='Test diff-highlight'
+
+CURR_DIR=$(pwd)
+TEST_OUTPUT_DIRECTORY=$(pwd)
+TEST_DIRECTORY="$CURR_DIR"/../../../t
+DIFF_HIGHLIGHT="$CURR_DIR"/../diff-highlight
+
+CW="$(printf "\033[7m")"	# white
+CR="$(printf "\033[27m")"	# reset
+
+. "$TEST_DIRECTORY"/test-lib.sh
+
+if ! test_have_prereq PERL
+then
+	skip_all='skipping diff-highlight tests; perl not available'
+	test_done
+fi
+
+# dh_test is a test helper function which takes 3 file names as parameters. The
+# first 2 files are used to generate diff and commit output, which is then
+# piped through diff-highlight. The 3rd file should contain the expected output
+# of diff-highlight (minus the diff/commit header, ie. everything after and
+# including the first @@ line).
+dh_test () {
+	a="$1" b="$2" &&
+
+	cat >patch.exp &&
+
+	{
+		cat "$a" >file &&
+		git add file &&
+		git commit -m "Add a file" &&
+
+		cat "$b" >file &&
+		git diff file >diff.raw &&
+		git commit -a -m "Update a file" &&
+		git show >commit.raw
+	} >/dev/null &&
+
+	"$DIFF_HIGHLIGHT" <diff.raw | test_strip_patch_header >diff.act &&
+	"$DIFF_HIGHLIGHT" <commit.raw | test_strip_patch_header >commit.act &&
+	test_cmp patch.exp diff.act &&
+	test_cmp patch.exp commit.act
+}
+
+test_strip_patch_header () {
+	sed -n '/^@@/,$p' $*
+}
+
+# dh_test_setup_history generates a contrived graph such that we have at least
+# 1 nesting (E) and 2 nestings (F).
+#
+#	      A branch
+#	     /
+#	D---E---F master
+#
+#	git log --all --graph
+#	* commit
+#	|    A
+#	| * commit
+#	| |    F
+#	| * commit
+#	|/
+#	|    E
+#	* commit
+#	     D
+#
+dh_test_setup_history () {
+	echo "file1" >file1 &&
+	echo "file2" >file2 &&
+	echo "file3" >file3 &&
+
+	cat file1 >file &&
+	git add file &&
+	git commit -m "D" &&
+
+	git checkout -b branch &&
+	cat file2 >file &&
+	git commit -a -m "A" &&
+
+	git checkout master &&
+	cat file2 >file &&
+	git commit -a -m "E" &&
+
+	cat file3 >file &&
+	git commit -a -m "F"
+}
+
+left_trim () {
+	"$PERL_PATH" -pe 's/^\s+//'
+}
+
+trim_graph () {
+	# graphs start with * or |
+	# followed by a space or / or \
+	"$PERL_PATH" -pe 's@^((\*|\|)( |/|\\))+@@'
+}
+
+test_expect_success 'diff-highlight highlights the beginning of a line' '
+	cat >a <<-\EOF &&
+		aaa
+		bbb
+		ccc
+	EOF
+
+	cat >b <<-\EOF &&
+		aaa
+		0bb
+		ccc
+	EOF
+
+	dh_test a b <<-EOF
+		@@ -1,3 +1,3 @@
+		 aaa
+		-${CW}b${CR}bb
+		+${CW}0${CR}bb
+		 ccc
+	EOF
+'
+
+test_expect_success 'diff-highlight highlights the end of a line' '
+	cat >a <<-\EOF &&
+		aaa
+		bbb
+		ccc
+	EOF
+
+	cat >b <<-\EOF &&
+		aaa
+		bb0
+		ccc
+	EOF
+
+	dh_test a b <<-EOF
+		@@ -1,3 +1,3 @@
+		 aaa
+		-bb${CW}b${CR}
+		+bb${CW}0${CR}
+		 ccc
+	EOF
+'
+
+test_expect_success 'diff-highlight highlights the middle of a line' '
+	cat >a <<-\EOF &&
+		aaa
+		bbb
+		ccc
+	EOF
+
+	cat >b <<-\EOF &&
+		aaa
+		b0b
+		ccc
+	EOF
+
+	dh_test a b <<-EOF
+		@@ -1,3 +1,3 @@
+		 aaa
+		-b${CW}b${CR}b
+		+b${CW}0${CR}b
+		 ccc
+	EOF
+'
+
+test_expect_success 'diff-highlight does not highlight whole line' '
+	cat >a <<-\EOF &&
+		aaa
+		bbb
+		ccc
+	EOF
+
+	cat >b <<-\EOF &&
+		aaa
+		000
+		ccc
+	EOF
+
+	dh_test a b <<-EOF
+		@@ -1,3 +1,3 @@
+		 aaa
+		-bbb
+		+000
+		 ccc
+	EOF
+'
+
+test_expect_failure 'diff-highlight highlights mismatched hunk size' '
+	cat >a <<-\EOF &&
+		aaa
+		bbb
+	EOF
+
+	cat >b <<-\EOF &&
+		aaa
+		b0b
+		ccc
+	EOF
+
+	dh_test a b <<-EOF
+		@@ -1,3 +1,3 @@
+		 aaa
+		-b${CW}b${CR}b
+		+b${CW}0${CR}b
+		+ccc
+	EOF
+'
+
+# These two code points share the same leading byte in UTF-8 representation;
+# a naive byte-wise diff would highlight only the second byte.
+#
+#   - U+00f3 ("o" with acute)
+o_accent=$(printf '\303\263')
+#   - U+00f8 ("o" with stroke)
+o_stroke=$(printf '\303\270')
+
+test_expect_success 'diff-highlight treats multibyte utf-8 as a unit' '
+	echo "unic${o_accent}de" >a &&
+	echo "unic${o_stroke}de" >b &&
+	dh_test a b <<-EOF
+		@@ -1 +1 @@
+		-unic${CW}${o_accent}${CR}de
+		+unic${CW}${o_stroke}${CR}de
+	EOF
+'
+
+# Unlike the UTF-8 above, these are combining code points which are meant
+# to modify the character preceding them:
+#
+#   - U+0301 (combining acute accent)
+combine_accent=$(printf '\314\201')
+#   - U+0302 (combining circumflex)
+combine_circum=$(printf '\314\202')
+
+test_expect_failure 'diff-highlight treats combining code points as a unit' '
+	echo "unico${combine_accent}de" >a &&
+	echo "unico${combine_circum}de" >b &&
+	dh_test a b <<-EOF
+		@@ -1 +1 @@
+		-unic${CW}o${combine_accent}${CR}de
+		+unic${CW}o${combine_circum}${CR}de
+	EOF
+'
+
+test_expect_success 'diff-highlight works with the --graph option' '
+	dh_test_setup_history &&
+
+	# topo-order so that the order of the commits is the same as with --graph
+	# trim graph elements so we can do a diff
+	# trim leading space because our trim_graph is not perfect
+	git log --branches -p --topo-order |
+		"$DIFF_HIGHLIGHT" | left_trim >graph.exp &&
+	git log --branches -p --graph |
+		"$DIFF_HIGHLIGHT" | trim_graph | left_trim >graph.act &&
+	test_cmp graph.exp graph.act
+'
+
+# Most combined diffs won't meet diff-highlight's line-number filter. So we
+# create one here where one side drops a line and the other modifies it. That
+# should result in a diff like:
+#
+#    - modified content
+#    ++resolved content
+#
+# which naively looks like one side added "+resolved".
+test_expect_success 'diff-highlight ignores combined diffs' '
+	echo "content" >file &&
+	git add file &&
+	git commit -m base &&
+
+	>file &&
+	git commit -am master &&
+
+	git checkout -b other HEAD^ &&
+	echo "modified content" >file &&
+	git commit -am other &&
+
+	test_must_fail git merge master &&
+	echo "resolved content" >file &&
+	git commit -am resolved &&
+
+	cat >expect <<-\EOF &&
+	--- a/file
+	+++ b/file
+	@@@ -1,1 -1,0 +1,1 @@@
+	- modified content
+	++resolved content
+	EOF
+
+	git show -c | "$DIFF_HIGHLIGHT" >actual.raw &&
+	sed -n "/^---/,\$p" <actual.raw >actual &&
+	test_cmp expect actual
+'
+
+test_done