Re: [PATCH 6/8] gitweb: Highlight interesting parts of diff

On Mon, 13 Feb 2012, Michal Kiedrowicz wrote:

Jakub Narebski [off-list ref] wrote:

quoted

Michał Kiedrowicz [off-list ref] writes:

quoted

Reading diff output is sometimes very hard, even if it's colored,
especially if lines differ only in few characters.  This is often
true when a commit fixes a typo or renames some variables or
functions.

This is certainly nice feature to have.  I think most tools that
implement side-by-side diff implement this too.

quoted

This commit teaches gitweb to highlight characters that are
different between old and new line.  This should work in the
similar manner as in Trac or GitHub.

Doe you have URLs with good examples of such diff refinement
highlighting (GNU Emacs ediff/emerge terminology) / highlighting
differing segments (diff-highlight terminology)?

I haven't found *examples* on GitHub and Trac sites, but what about
these ones:

https://github.com/gitster/git/commit/8cad4744ee37ebec1d9491a1381ec1771a1ba795
http://trac.edgewall.org/changeset/10973

Thanks.  That is what I meant by "good examples".  Perhaps they should
be put in the commit message?

BTW GitHub is closed source, but we can check what algorithm does Trac
use for diff refinement highlighting (highlighting changed portions of
diff).

quoted

quoted

The code that compares lines is based on
contrib/diff-highlight/diff-highlight, except that it works with
multiline changes too.  It also won't highlight lines that are
completely different because that would only make the output
unreadable.

So what does it look like?  From the contrib/diff-highlight/README I
guess that it finds common prefix and common suffix, and highlights
the rest, which includes change.  

Yes.

quoted

It doesn't implement LCS / diff
algorithm like e.g. tkdiff does for its diff refinement highlighting,
isn't it?

I doesn't. I share the Jeff's opinion that:
a) Jeff's approach is "good enough"
b) LCS on bytes could be very confusing if it marked few sets of
characters.

I wonder if we can use --diff-words for diff refinement highlighting,
i.e. LCS on words.

Anyway Jeff's approach is a bit limited, in that it would work only for
change that does not involve adding newlines, for example splitting
overly long line when changing something.

See for example line 1786 (in pre-image) in http://trac.edgewall.org/changeset/10973
 

quoted

By completly different you mean that they do not have common prefix or
common suffix (at least one of them), isn't it?

BTW. is it "at least one of prefix or suffix are non-empty" or "both prefix
and suffix are non-empty"?

Yes, but I also don't highlight lines which prefix/suffix consists only
of whitespace (This is quite common). 

O.K., that is quite sensible.

I would also consider ignoring prefixes/suffixes with punctuation, like:

	- * I like you.
	+ * Alice had a little lamb.

But this patch doesn't implement this feature yet, isn't it?

Well, here is another idea: do not highlight if sum of prefix and suffix
lengths are less than some threshold, e.g. 2 characters not including 
whitespace, or some percentage with respect to total line length.

quoted

quoted

+# Highlight characters from $prefix to $suffix and escape HTML.
+# $str is a reference to the array of characters.
+sub esc_html_mark_range {
+	my ($str, $prefix, $suffix) = @_;
+
+	# Don't generate empty <span> element.
+	if ($prefix == $suffix + 1) {
+		return esc_html(join('', @$str), -nbsp=>1);
+	}
+
+	my $before = join('', @{$str}[0..($prefix - 1)]);
+	my $marked = join('', @{$str}[$prefix..$suffix]);
+	my $after  = join('', @{$str}[($suffix + 1)..$#{$str}]);

It would be nicer with 'part' from List::MoreUtils... but that module
is unfortunately not in core.

quoted

Eeeeeek!  First you split into letters, in caller at that, then join?
Why not pass striung ($str suggests string not array of characters),
and use substr instead?

[Please disregard this and the next paragraph at first reading]

I will rename $str to something more self describing.

Please do.

BTW. don't you assume here that both common prefix and common suffix
are non-empty?
 
[...]

quoted

quoted

+
+# Format removed and added line, mark changed part and HTML-format
them.

You should probably add here that this code is taken from
diff-highlight in contrib area, isn't it?

True.

And perhaps not the changes from diff-highlight, unless you meant to
send them upstream for inclusion.

quoted

quoted

+sub format_rem_add_line {
+	my ($rem, $add) = @_;
+	my @r = split(//, $rem);
+	my @a = split(//, $add);

BTW the name of variable can be just @add and @rem.

quoted

quoted

+	my ($esc_rem, $esc_add);
+	my ($prefix, $suffix_rem, $suffix_add) = (1, $#r, $#a);

It is not as much $prefix, as $prefix_len, isn't it?  

Yes.

quoted

Shouldn't
$prefix / $prefix_len start from 0, not from 1?

It starts from 1 because it skips first +/-. It should become obvious
after reading the comment from last patch :).

+	# In combined diff we must ignore two +/- characters.
+	$prefix = 2 if ($is_combined);

Anyway comment about that fact would be nice.
 

quoted

quoted

+	my ($prefix_is_space, $suffix_is_space) = (1, 1);
+
+	while ($prefix < @r && $prefix < @a) {
+		last if ($r[$prefix] ne $a[$prefix]);
+
+		$prefix_is_space = 0 if ($r[$prefix] !~ /\s/);
+		$prefix++;
+	}

Ah, I see that it is easier to find common prefix by treating string
as array of characters.

Though I wonder if it wouldn't be easier to use trick of XOR-ing two
strings (see "Bitwise String Operators" in perlop(1)):

        my $xor = "$rem" ^ "$add";

and finding starting sequence of "\0", which denote common prefix.


Though this and the following is a nice implementation of
algorithm... as it would be implemented in C.  Nevermind, it might be
good enough...

The splitting and comparing by characters is taken from diff-highlight.
I don't think it's worth changing here.

You are right.

I'll try to come with hacky algorithm using string bitwise xor and regexp,
and benchmark it comparing to your C-like solution, but it can be left for
later (simple is better than clever, usually).
 

quoted

quoted

+	while ($suffix_rem >= $prefix && $suffix_add >= $prefix) {
+		last if ($r[$suffix_rem] ne $a[$suffix_add]);
+
+		$suffix_is_space = 0 if ($r[$suffix_rem] !~ /\s/);
+		$suffix_rem--;
+		$suffix_add--;
+	}

BTW., perhaps using single negative $suffix_len instead of separate
$suffix_rem_pos and $suffix_add_pos would make code simpler and easier
to understand?

I'll try that.

I think this should just work, and it would be one variable less to
track.
 

quoted

quoted

 # HTML-format diff context, removed and added lines.
 sub format_ctx_rem_add_lines {
-	my ($ctx, $rem, $add) = @_;
+	my ($ctx, $rem, $add, $is_combined) = @_;
 	my (@new_ctx, @new_rem, @new_add);
+	my $num_add_lines = @$add;

Why is this temporary variable needed?  If you are not sure that ==
operator enforces scalar context on both arguments you can always
write

  scalar @$add == scalar @$rem

You read my mind.

BTW. the same comment applies to patch adding support for highlighting
changed part in combined diff.
 

quoted

The original contrib/diff-highlight works only for single changed line
(single removed and single added).  You make this code work also for
the case where number of aded lines is equal to the number of removed
lines, and assume that subsequent changed lines in preimage
correcponds to subsequent changed lines in postimage, [...]

[...]

quoted

This is not described in commit message, I think.

-- 
Jakub Narebski
Poland