From 40e174d5364910750413d94b5417e57d108190ef Mon Sep 17 00:00:00 2001
From: Ragnar Ouchterlony
Date: Sun, 13 Sep 2009 19:36:35 +0200
Subject: First version of side-by-side diff.

This constitutes the first prototype of a side-by-side diff. It is not
possible to switch between unidiff and side-by-side diff at all at this
stage.

Signed-off-by: Ragnar Ouchterlony <ragnar@lysator.liu.se>
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
---
 cgit.css | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

(limited to 'cgit.css')

diff --git a/cgit.css b/cgit.css
index c47ebc9..bf58b8a 100644
--- a/cgit.css
+++ b/cgit.css
@@ -601,3 +601,38 @@ table.hgraph div.bar {
 	background-color: #eee;
 	height: 1em;
 }
+
+table.ssdiff td.add {
+	color: black;
+	background: #afa;
+}
+
+table.ssdiff td.add_dark {
+	color: black;
+	background: #9c9;
+}
+
+table.ssdiff td.del {
+	color: black;
+	background: #faa;
+}
+
+table.ssdiff td.del_dark {
+	color: black;
+	background: #c99;
+}
+
+table.ssdiff td.changed {
+	color: black;
+	background: #ffa;
+}
+
+table.ssdiff td.changed_dark {
+	color: black;
+	background: #cc9;
+}
+
+table.ssdiff td.hunk {
+	color: #black;
+	background: #ccf;
+}
-- 
cgit v1.2.3-70-g09d2


From 207cc34711039329b41345f716bf421a88a6fd0a Mon Sep 17 00:00:00 2001
From: Ragnar Ouchterlony
Date: Tue, 15 Sep 2009 19:44:37 +0200
Subject: Polishing of how the side-by-side diff looks.

Aligned all different files, so that all side-by-side tables look
the same. Also made sure that the tables take up the whole browser
width.

Also various changes to the css to make things easier on the eye.

Signed-off-by: Ragnar Ouchterlony <ragnar@lysator.liu.se>
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
---
 cgit.css    | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 ui-diff.c   | 27 ++++++++++++++-----------
 ui-ssdiff.c | 30 +++++++++++++++++-----------
 ui-ssdiff.h |  3 ++-
 4 files changed, 96 insertions(+), 30 deletions(-)

(limited to 'cgit.css')

diff --git a/cgit.css b/cgit.css
index bf58b8a..3f37165 100644
--- a/cgit.css
+++ b/cgit.css
@@ -602,37 +602,91 @@ table.hgraph div.bar {
 	height: 1em;
 }
 
+table.ssdiff {
+	width: 100%;
+}
+
+table.ssdiff td {
+	font-size: 75%;
+	font-family: monospace;
+	white-space: pre;
+	padding: 1px 4px 1px 4px;
+	border-left: solid 1px #aaa;
+	border-right: solid 1px #aaa;
+}
+
 table.ssdiff td.add {
 	color: black;
-	background: #afa;
+	background: #cfc;
+	min-width: 50%;
 }
 
 table.ssdiff td.add_dark {
 	color: black;
-	background: #9c9;
+	background: #aca;
+	min-width: 50%;
 }
 
 table.ssdiff td.del {
 	color: black;
-	background: #faa;
+	background: #fcc;
+	min-width: 50%;
 }
 
 table.ssdiff td.del_dark {
 	color: black;
-	background: #c99;
+	background: #caa;
+	min-width: 50%;
 }
 
 table.ssdiff td.changed {
 	color: black;
-	background: #ffa;
+	background: #ffc;
+	min-width: 50%;
 }
 
 table.ssdiff td.changed_dark {
 	color: black;
-	background: #cc9;
+	background: #cca;
+	min-width: 50%;
+}
+
+table.ssdiff td.lineno {
+	color: black;
+	background: #eee;
+	text-align: right;
+	width: 3em;
+	min-width: 3em;
 }
 
 table.ssdiff td.hunk {
 	color: #black;
 	background: #ccf;
+	border-top: solid 1px #aaa;
+	border-bottom: solid 1px #aaa;
 }
+
+table.ssdiff td.head {
+	border-top: solid 1px #aaa;
+	border-bottom: solid 1px #aaa;
+}
+
+table.ssdiff td.head div.head {
+	font-weight: bold;
+	color: black;
+}
+
+table.ssdiff td.foot {
+	border-top: solid 1px #aaa;
+        border-left: none;
+        border-right: none;
+        border-bottom: none;
+}
+
+table.ssdiff td.space {
+	border: none;
+}
+
+table.ssdiff td.space div {
+	min-height: 3em;
+}
\ No newline at end of file
diff --git a/ui-diff.c b/ui-diff.c
index 42e81ac..b21c2c1 100644
--- a/ui-diff.c
+++ b/ui-diff.c
@@ -246,8 +246,6 @@ static void header(unsigned char *sha1, char *path1, int mode1,
 			html_txt(path2);
 	}
 	html("</div>");
-	if (use_ssdiff)
-		cgit_ssdiff_header();
 }
 
 static void print_ssdiff_link()
@@ -270,24 +268,26 @@ static void filepair_cb(struct diff_filepair *pair)
 	int binary = 0;
 	linediff_fn print_line_fn = print_line;
 
-	header(pair->one->sha1, pair->one->path, pair->one->mode,
-	       pair->two->sha1, pair->two->path, pair->two->mode);
 	if (use_ssdiff) {
-		cgit_ssdiff_header();
+		cgit_ssdiff_header_begin();
 		print_line_fn = cgit_ssdiff_line_cb;
 	}
+	header(pair->one->sha1, pair->one->path, pair->one->mode,
+	       pair->two->sha1, pair->two->path, pair->two->mode);
+	if (use_ssdiff)
+		cgit_ssdiff_header_end();
 	if (S_ISGITLINK(pair->one->mode) || S_ISGITLINK(pair->two->mode)) {
 		if (S_ISGITLINK(pair->one->mode))
-			print_line(fmt("-Subproject %s", sha1_to_hex(pair->one->sha1)), 52);
+			print_line_fn(fmt("-Subproject %s", sha1_to_hex(pair->one->sha1)), 52);
 		if (S_ISGITLINK(pair->two->mode))
-			print_line(fmt("+Subproject %s", sha1_to_hex(pair->two->sha1)), 52);
+			print_line_fn(fmt("+Subproject %s", sha1_to_hex(pair->two->sha1)), 52);
 		return;
 	}
 	if (cgit_diff_files(pair->one->sha1, pair->two->sha1, &old_size,
 			    &new_size, &binary, print_line_fn))
 		cgit_print_error("Error running diff");
 	if (binary)
-		html("Binary files differ");
+		print_line_fn(" Binary files differ", 20);
 	if (use_ssdiff)
 		cgit_ssdiff_footer();
 }
@@ -334,9 +334,14 @@ void cgit_print_diff(const char *new_rev, const char *old_rev, const char *prefi
 	print_ssdiff_link();
 	cgit_print_diffstat(old_rev_sha1, new_rev_sha1);
 
-	html("<table summary='diff' class='diff'>");
-	html("<tr><td>");
+	if (use_ssdiff) {
+		html("<table summary='ssdiff' class='ssdiff'>");
+	} else {
+		html("<table summary='diff' class='diff'>");
+		html("<tr><td>");
+	}
 	cgit_diff_tree(old_rev_sha1, new_rev_sha1, filepair_cb, prefix);
-	html("</td></tr>");
+	if (!use_ssdiff)
+		html("</td></tr>");
 	html("</table>");
 }
diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 3591ab4..8215051 100644
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -40,9 +40,9 @@ static char *replace_tabs(char *line)
 {
 	char *prev_buf = line;
 	char *cur_buf;
-        int linelen = strlen(line);
+	int linelen = strlen(line);
 	int n_tabs = 0;
-        int i;
+	int i;
 	char *result;
 	char *spaces = "        ";
 
@@ -52,10 +52,10 @@ static char *replace_tabs(char *line)
 		return result;
 	}
 
-        for (i = 0; i < linelen; i++)
+	for (i = 0; i < linelen; i++)
 		if (line[i] == '\t')
 			n_tabs += 1;
-        result = xmalloc(linelen + n_tabs * 8 + 1);
+	result = xmalloc(linelen + n_tabs * 8 + 1);
 	result[0] = '\0';
 
 	while (1) {
@@ -106,10 +106,10 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
 {
 	html("<tr>");
 	if (old_line_no > 0)
-		htmlf("<td class='%s'>%d </td><td class='%s'>", class,
+		htmlf("<td class='lineno'>%d</td><td class='%s'>",
 		      old_line_no, class);
 	else
-		htmlf("<td class='%s_dark'>  </td><td class='%s_dark'>", class, class);
+		htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
 
 	if (old_line) {
 		old_line = replace_tabs(old_line + 1);
@@ -117,13 +117,13 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
 		free(old_line);
 	}
 
-	html("  </td>");
+	html("</td>");
 
 	if (new_line_no > 0)
-		htmlf("<td class='%s'>  %d </td><td class='%s'>", class,
+		htmlf("<td class='lineno'>%d</td><td class='%s'>",
 		      new_line_no, class);
 	else
-		htmlf("<td class='%s_dark'>  </td><td class='%s_dark'>", class, class);
+		htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
 
 	if (new_line) {
 		new_line = replace_tabs(new_line + 1);
@@ -249,16 +249,22 @@ void cgit_ssdiff_line_cb(char *line, int len)
 	line[len - 1] = c;
 }
 
-void cgit_ssdiff_header()
+void cgit_ssdiff_header_begin()
 {
 	current_old_line = 0;
 	current_new_line = 0;
-	html("<table class='ssdiff'>");
+	html("<tr><td class='space' colspan='4'><div></div></td></tr>");
+	html("<tr><td class='head' colspan='4'>");
+}
+
+void cgit_ssdiff_header_end()
+{
+	html("</td><tr>");
 }
 
 void cgit_ssdiff_footer()
 {
 	if (deferred_old || deferred_new)
 		cgit_ssdiff_print_deferred_lines();
-	html("</table>");
+	html("<tr><td class='foot' colspan='4'></td></tr>");
 }
diff --git a/ui-ssdiff.h b/ui-ssdiff.h
index a0b1efe..64b4b12 100644
--- a/ui-ssdiff.h
+++ b/ui-ssdiff.h
@@ -5,7 +5,8 @@ extern void cgit_ssdiff_print_deferred_lines();
 
 extern void cgit_ssdiff_line_cb(char *line, int len);
 
-extern void cgit_ssdiff_header();
+extern void cgit_ssdiff_header_begin();
+extern void cgit_ssdiff_header_end();
 
 extern void cgit_ssdiff_footer();
 
-- 
cgit v1.2.3-70-g09d2


From 735e15e38a484bf0daa98776fa7cde270a271cda Mon Sep 17 00:00:00 2001
From: Ragnar Ouchterlony
Date: Sun, 25 Oct 2009 18:13:22 +0100
Subject: In side-by-side diff, add support for marking individual characters.

Refuses to do so if the left hand side of the diff has different amount of
differing lines to the right hand side to avoid confusion.

Note that I use the naive dynamic programming approach for calculating the
longest common subsequence. We could probably be more efficient by using a
better algorithm. The LCS calculating function is O(n*m) and uses up n*m
amount of memory too (so if we we compare two strings of length 100, I use
an array of 10000 for calculating the LCS). Might want to not calculate LCS
if the length of the line is too large.

Signed-off-by: Ragnar Ouchterlony <ragnar@lysator.liu.se>
---
 cgit.css    |  10 +++++
 ui-ssdiff.c | 145 +++++++++++++++++++++++++++++++++++++++++++++++++-----------
 2 files changed, 130 insertions(+), 25 deletions(-)

(limited to 'cgit.css')

diff --git a/cgit.css b/cgit.css
index 3f37165..9e6d2a4 100644
--- a/cgit.css
+++ b/cgit.css
@@ -627,6 +627,11 @@ table.ssdiff td.add_dark {
 	min-width: 50%;
 }
 
+table.ssdiff span.add {
+	background: #cfc;
+	font-weight: bold;
+}
+
 table.ssdiff td.del {
 	color: black;
 	background: #fcc;
@@ -639,6 +644,11 @@ table.ssdiff td.del_dark {
 	min-width: 50%;
 }
 
+table.ssdiff span.del {
+	background: #fcc;
+	font-weight: bold;
+}
+
 table.ssdiff td.changed {
 	color: black;
 	background: #ffc;
diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 5673642..408e620 100644
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -15,6 +15,52 @@ struct deferred_lines {
 static struct deferred_lines *deferred_old, *deferred_old_last;
 static struct deferred_lines *deferred_new, *deferred_new_last;
 
+static char *longest_common_subsequence(char *A, char *B)
+{
+	int i, j, ri;
+	int m = strlen(A);
+	int n = strlen(B);
+	int L[m + 1][n + 1];
+	int tmp1, tmp2;
+	int lcs_length;
+	char *result;
+
+	for (i = m; i >= 0; i--) {
+		for (j = n; j >= 0; j--) {
+			if (A[i] == '\0' || B[j] == '\0') {
+				L[i][j] = 0;
+			} else if (A[i] == B[j]) {
+				L[i][j] = 1 + L[i + 1][j + 1];
+			} else {
+				tmp1 = L[i + 1][j];
+				tmp2 = L[i][j + 1];
+				L[i][j] = (tmp1 > tmp2 ? tmp1 : tmp2);
+			}
+		}
+	}
+
+	lcs_length = L[0][0];
+	result = xmalloc(lcs_length + 2);
+	memset(result, 0, sizeof(*result) * (lcs_length + 2));
+
+	ri = 0;
+	i = 0;
+	j = 0;
+	while (i < m && j < n) {
+		if (A[i] == B[j]) {
+			result[ri] = A[i];
+			ri += 1;
+			i += 1;
+			j += 1;
+		} else if (L[i + 1][j] >= L[i][j + 1]) {
+			i += 1;
+		} else {
+			j += 1;
+		}
+	}
+	return result;
+}
+
 static int line_from_hunk(char *line, char type)
 {
 	char *buf1, *buf2;
@@ -73,6 +119,17 @@ static char *replace_tabs(char *line)
 	return result;
 }
 
+static int calc_deferred_lines(struct deferred_lines *start)
+{
+	struct deferred_lines *item = start;
+	int result = 0;
+	while (item) {
+		result += 1;
+		item = item->next;
+	}
+	return result;
+}
+
 static void deferred_old_add(char *line, int line_no)
 {
 	struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));
@@ -101,9 +158,45 @@ static void deferred_new_add(char *line, int line_no)
 	}
 }
 
-static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
-			      int new_line_no, char *new_line)
+static void print_part_with_lcs(char *class, char *line, char *lcs)
+{
+	int line_len = strlen(line);
+	int i, j;
+	char c[2] = " ";
+	int same = 1;
+
+	j = 0;
+	for (i = 0; i < line_len; i++) {
+		c[0] = line[i];
+		if (same) {
+			if (line[i] == lcs[j])
+				j += 1;
+			else {
+				same = 0;
+				htmlf("<span class='%s'>", class);
+			}
+		} else if (line[i] == lcs[j]) {
+			same = 1;
+			htmlf("</span>");
+			j += 1;
+		}
+		html_txt(c);
+	}
+}
+
+static void print_ssdiff_line(char *class,
+			      int old_line_no,
+			      char *old_line,
+			      int new_line_no,
+			      char *new_line, int individual_chars)
 {
+	char *lcs = NULL;
+	if (old_line)
+		old_line = replace_tabs(old_line + 1);
+	if (new_line)
+		new_line = replace_tabs(new_line + 1);
+	if (individual_chars && old_line && new_line)
+		lcs = longest_common_subsequence(old_line, new_line);
 	html("<tr>");
 	if (old_line_no > 0)
 		htmlf("<td class='lineno'>%d</td><td class='%s'>",
@@ -112,15 +205,14 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
 		htmlf("<td class='lineno'></td><td class='%s'>", class);
 	else
 		htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
-
 	if (old_line) {
-		old_line = replace_tabs(old_line + 1);
-		html_txt(old_line);
-		free(old_line);
+		if (lcs)
+			print_part_with_lcs("del", old_line, lcs);
+		else
+			html_txt(old_line);
 	}
 
 	html("</td>");
-
 	if (new_line_no > 0)
 		htmlf("<td class='lineno'>%d</td><td class='%s'>",
 		      new_line_no, class);
@@ -128,24 +220,29 @@ static void print_ssdiff_line(char *class, int old_line_no, char *old_line,
 		htmlf("<td class='lineno'></td><td class='%s'>", class);
 	else
 		htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
-
 	if (new_line) {
-		new_line = replace_tabs(new_line + 1);
-		html_txt(new_line);
-		free(new_line);
+		if (lcs)
+			print_part_with_lcs("add", new_line, lcs);
+		else
+			html_txt(new_line);
 	}
 
 	html("</td></tr>");
+	if (lcs)
+		free(lcs);
+	if (new_line)
+		free(new_line);
+	if (old_line)
+		free(old_line);
 }
 
 static void print_deferred_old_lines()
 {
 	struct deferred_lines *iter_old, *tmp;
-
 	iter_old = deferred_old;
 	while (iter_old) {
 		print_ssdiff_line("del", iter_old->line_no,
-				  iter_old->line, -1, NULL);
+				  iter_old->line, -1, NULL, 0);
 		tmp = iter_old->next;
 		free(iter_old);
 		iter_old = tmp;
@@ -155,11 +252,10 @@ static void print_deferred_old_lines()
 static void print_deferred_new_lines()
 {
 	struct deferred_lines *iter_new, *tmp;
-
 	iter_new = deferred_new;
 	while (iter_new) {
-		print_ssdiff_line("add", -1, NULL, iter_new->line_no,
-				  iter_new->line);
+		print_ssdiff_line("add", -1, NULL,
+				  iter_new->line_no, iter_new->line, 0);
 		tmp = iter_new->next;
 		free(iter_new);
 		iter_new = tmp;
@@ -169,6 +265,9 @@ static void print_deferred_new_lines()
 static void print_deferred_changed_lines()
 {
 	struct deferred_lines *iter_old, *iter_new, *tmp;
+	int n_old_lines = calc_deferred_lines(deferred_old);
+	int n_new_lines = calc_deferred_lines(deferred_new);
+	int individual_chars = (n_old_lines == n_new_lines ? 1 : 0);
 
 	iter_old = deferred_old;
 	iter_new = deferred_new;
@@ -176,14 +275,14 @@ static void print_deferred_changed_lines()
 		if (iter_old && iter_new)
 			print_ssdiff_line("changed", iter_old->line_no,
 					  iter_old->line,
-					  iter_new->line_no, iter_new->line);
+					  iter_new->line_no, iter_new->line,
+					  individual_chars);
 		else if (iter_old)
 			print_ssdiff_line("changed", iter_old->line_no,
-					  iter_old->line, -1, NULL);
+					  iter_old->line, -1, NULL, 0);
 		else if (iter_new)
 			print_ssdiff_line("changed", -1, NULL,
-					  iter_new->line_no, iter_new->line);
-
+					  iter_new->line_no, iter_new->line, 0);
 		if (iter_old) {
 			tmp = iter_old->next;
 			free(iter_old);
@@ -202,14 +301,12 @@ void cgit_ssdiff_print_deferred_lines()
 {
 	if (!deferred_old && !deferred_new)
 		return;
-
 	if (deferred_old && !deferred_new)
 		print_deferred_old_lines();
 	else if (!deferred_old && deferred_new)
 		print_deferred_new_lines();
 	else
 		print_deferred_changed_lines();
-
 	deferred_old = deferred_old_last = NULL;
 	deferred_new = deferred_new_last = NULL;
 }
@@ -220,9 +317,7 @@ void cgit_ssdiff_print_deferred_lines()
 void cgit_ssdiff_line_cb(char *line, int len)
 {
 	char c = line[len - 1];
-
 	line[len - 1] = '\0';
-
 	if (line[0] == '@') {
 		current_old_line = line_from_hunk(line, '-');
 		current_new_line = line_from_hunk(line, '+');
@@ -232,7 +327,7 @@ void cgit_ssdiff_line_cb(char *line, int len)
 		if (deferred_old || deferred_new)
 			cgit_ssdiff_print_deferred_lines();
 		print_ssdiff_line("ctx", current_old_line, line,
-				  current_new_line, line);
+				  current_new_line, line, 0);
 		current_old_line += 1;
 		current_new_line += 1;
 	} else if (line[0] == '+') {
-- 
cgit v1.2.3-70-g09d2