1 file changed, 253 insertions, 248 deletions
diff --git a/source/ui-ssdiff.c b/source/ui-ssdiff.c
index e4472c4..2ea7021 100644
--- a/source/ui-ssdiff.c
+++ b/source/ui-ssdiff.c
@@ -1,185 +1,131 @@
+/*
+ * The side by side rendering of a diff, the layout a reader gets instead of
+ * the unified listing. ui-diff.c drives it, handing over each line xdiff
+ * produces and calling in around the header and the footer of every file.
+ * Removed and added lines are held back until their run ends, so that the two
+ * sides can be paired into a row apiece. When a run has as many removals as
+ * additions the paired lines are compared character by character, and what
+ * differs within them is marked.
+ */
+
 #include "cgit.h"
-#include "ui-ssdiff.h"
 #include "html.h"
-#include "ui-shared.h"
 #include "ui-diff.h"
+#include "ui-shared.h"
+#include "ui-ssdiff.h"
 
-extern int use_ssdiff;
-
-static int current_old_line, current_new_line;
-static int **L = NULL;
+// The stylesheet sets no tab-size and tabs are expanded here rather than left
+// to the browser, so this has to be the width a browser would pick on its own.
+#define TAB_WIDTH 8
 
-struct deferred_lines {
+// One line held back until its run ends, owning the copy taken of it.
+struct deferred_line {
 	int line_no;
 	char *line;
-	struct deferred_lines *next;
+	struct deferred_line *next;
 };
 
-static struct deferred_lines *deferred_old, *deferred_old_last;
-static struct deferred_lines *deferred_new, *deferred_new_last;
+static int current_old_line, current_new_line;
+static int **lcs_table;
+static struct deferred_line *deferred_old, *deferred_old_last;
+static struct deferred_line *deferred_new, *deferred_new_last;
 
 /*
- * The table does not need clearing between calls. The fill below assigns
- * every cell in [0,m] x [0,n] before anything reads it: a read only happens
- * where both lines still have a character, so it never reaches past row m or
- * column n, and the loops run downwards so the neighbour is always already
- * written. Clearing the whole table on every changed line pair cost more than
- * the comparison it was preparing for.
+ * The table is reused by every comparison and nothing clears it in between,
+ * because the fill in longest_common_subsequence works back from the far
+ * corner and writes every cell it goes on to read. Clearing it for each pair
+ * of lines cost more than the comparison it was preparing for.
  */
 static void create_lcs_table(void)
 {
 	int i;
 
-	if (L != NULL)
+	if (lcs_table)
 		return;
 
-	// xcalloc will die if we ran out of memory;
-	// not very helpful for debugging
-	L = (int**)xcalloc(MAX_SSDIFF_M, sizeof(int *));
-	*L = (int*)xcalloc(MAX_SSDIFF_SIZE, sizeof(int));
-
-	for (i = 1; i < MAX_SSDIFF_M; i++) {
-		L[i] = *L + i * MAX_SSDIFF_N;
-	}
+	lcs_table = xcalloc(MAX_SSDIFF_M, sizeof(int *));
+	lcs_table[0] = xcalloc(MAX_SSDIFF_SIZE, sizeof(int));
+	for (i = 1; i < MAX_SSDIFF_M; i++)
+		lcs_table[i] = lcs_table[0] + i * MAX_SSDIFF_N;
 }
 
-static char *longest_common_subsequence(char *A, char *B)
+/*
+ * The characters the two lines have in common, in order, which the caller
+ * owns. A line too long for the table gets NULL back and is shown whole
+ * instead.
+ */
+static char *longest_common_subsequence(const char *old_line,
+					const char *new_line)
 {
-	int i, j, ri;
-	int m = strlen(A);
-	int n = strlen(B);
-	int tmp1, tmp2;
-	int lcs_length;
-	char *result;
-
-	// We bail if the lines are too long
-	if (m >= MAX_SSDIFF_M || n >= MAX_SSDIFF_N)
+	int old_len = strlen(old_line);
+	int new_len = strlen(new_line);
+	int i, j, pos, lcs_len;
+	char *lcs;
+
+	if (old_len >= MAX_SSDIFF_M || new_len >= MAX_SSDIFF_N)
 		return NULL;
 
 	create_lcs_table();
 
-	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];
+	for (i = old_len; i >= 0; i--) {
+		for (j = new_len; j >= 0; j--) {
+			if (old_line[i] == '\0' || new_line[j] == '\0') {
+				lcs_table[i][j] = 0;
+			} else if (old_line[i] == new_line[j]) {
+				lcs_table[i][j] = 1 + lcs_table[i + 1][j + 1];
 			} else {
-				tmp1 = L[i + 1][j];
-				tmp2 = L[i][j + 1];
-				L[i][j] = (tmp1 > tmp2 ? tmp1 : tmp2);
+				int drop_old = lcs_table[i + 1][j];
+				int drop_new = lcs_table[i][j + 1];
+
+				lcs_table[i][j] = (drop_old > drop_new ?
+						   drop_old : drop_new);
 			}
 		}
 	}
 
-	lcs_length = L[0][0];
-	result = xmalloc(lcs_length + 2);
-	memset(result, 0, sizeof(*result) * (lcs_length + 2));
+	lcs_len = lcs_table[0][0];
+	lcs = xmalloc(lcs_len + 2);
+	memset(lcs, 0, sizeof(*lcs) * (lcs_len + 2));
 
-	ri = 0;
+	pos = 0;
 	i = 0;
 	j = 0;
-	while (i < m && j < n) {
-		if (A[i] == B[j]) {
-			result[ri] = A[i];
-			ri += 1;
+	while (i < old_len && j < new_len) {
+		if (old_line[i] == new_line[j]) {
+			lcs[pos] = old_line[i];
+			pos += 1;
 			i += 1;
 			j += 1;
-		} else if (L[i + 1][j] >= L[i][j + 1]) {
+		} else if (lcs_table[i + 1][j] >= lcs_table[i][j + 1]) {
 			i += 1;
 		} else {
 			j += 1;
 		}
 	}
 
-	return result;
+	return lcs;
 }
 
-static int line_from_hunk(char *line, char type)
-{
-	char *p;
-	long res;
-
-	p = strchr(line, type);
-	if (p == NULL)
-		return 0;
-	p += 1;
-	// git omits the length when a hunk covers a single line, as in
-	// "@@ -1 +1 @@", so the number runs to whatever follows it rather than
-	// to a comma that may belong to the other side of the header or be
-	// missing altogether.
-	res = strtol(p, NULL, 10);
-	if (res < 0 || res > INT_MAX)
-		return 0;
-	return (int)res;
-}
-
-static char *replace_tabs(char *line)
+/*
+ * The line with its tabs expanded, which the caller owns. Appending as the
+ * line is walked replaces a loop that rescanned the rest of the input at every
+ * tab, which made a tab heavy line quadratic in its own length.
+ */
+static char *expand_tabs(const char *line)
 {
 	struct strbuf out = STRBUF_INIT;
 	const char *p;
 
-	// Each tab runs to the next eight-column stop. Walking the line once
-	// and appending replaces a loop that measured the result and rescanned
-	// the rest of the input at every tab, which made a tab-heavy line
-	// quadratic in its own length.
 	for (p = line; *p; p++) {
 		if (*p == '\t')
-			strbuf_addchars(&out, ' ', 8 - (out.len % 8));
+			strbuf_addchars(&out, ' ',
+					TAB_WIDTH - (out.len % TAB_WIDTH));
 		else
 			strbuf_addch(&out, *p);
 	}
 	return strbuf_detach(&out, NULL);
 }
 
-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));
-	item->line = xstrdup(line);
-	item->line_no = line_no;
-	item->next = NULL;
-	if (deferred_old) {
-		deferred_old_last->next = item;
-		deferred_old_last = item;
-	} else {
-		deferred_old = deferred_old_last = item;
-	}
-}
-
-static void deferred_new_add(char *line, int line_no)
-{
-	struct deferred_lines *item = xmalloc(sizeof(struct deferred_lines));
-	item->line = xstrdup(line);
-	item->line_no = line_no;
-	item->next = NULL;
-	if (deferred_new) {
-		deferred_new_last->next = item;
-		deferred_new_last = item;
-	} else {
-		deferred_new = deferred_new_last = item;
-	}
-}
-
-/* The item owns the copy of the line taken when it was deferred, so both go
- * together. print_ssdiff_line only reads the line and frees what it derives
- * from it, and never keeps the pointer it was handed. */
-static void free_deferred(struct deferred_lines *item)
-{
-	free(item->line);
-	free(item);
-}
-
 static void flush_run(struct strbuf *run)
 {
 	if (!run->len)
@@ -188,186 +134,240 @@ static void flush_run(struct strbuf *run)
 	strbuf_reset(run);
 }
 
-static void print_part_with_lcs(const char *class, char *line, char *lcs)
+/*
+ * A stretch that the other side does not share is escaped in one call because
+ * escaping a character at a time sent every character of every changed line
+ * through the output path on its own, which dominated this page.
+ */
+static void print_line_with_lcs(const char *class, const char *line,
+				const char *lcs)
 {
-	int line_len = strlen(line);
-	int i, j;
-	int same = 1;
+	int len = strlen(line);
+	int in_common = 1;
+	int matched = 0;
+	int i;
 	struct strbuf run = STRBUF_INIT;
 
-	// Collect each stretch that is wholly inside or wholly outside the
-	// common subsequence and escape it in one go. Escaping a character at a
-	// time meant a write syscall per character of every changed line, which
-	// dominated this page.
-	j = 0;
-	for (i = 0; i < line_len; i++) {
-		if (same) {
-			if (line[i] == lcs[j])
-				j += 1;
+	for (i = 0; i < len; i++) {
+		if (in_common) {
+			if (line[i] == lcs[matched])
+				matched += 1;
 			else {
-				same = 0;
+				in_common = 0;
 				flush_run(&run);
 				htmlf("<span class='%s'>", class);
 			}
-		} else if (line[i] == lcs[j]) {
-			same = 1;
+		} else if (line[i] == lcs[matched]) {
+			in_common = 1;
 			flush_run(&run);
 			html("</span>");
-			j += 1;
+			matched += 1;
 		}
 		strbuf_addch(&run, line[i]);
 	}
 	flush_run(&run);
-	if (!same)
+	if (!in_common)
 		html("</span>");
 	strbuf_release(&run);
 }
 
-static void print_ssdiff_line(const char *class,
-			      int old_line_no,
-			      char *old_line,
-			      int new_line_no,
-			      char *new_line, int individual_chars)
+static void print_lineno_cell(struct diff_filespec *file,
+			      const struct object_id *rev, int line_no)
+{
+	struct strbuf path = STRBUF_INIT;
+	char *anchor, *query, *fileurl;
+	const char *rev_hex;
+
+	anchor = cgit_fmt("n%d", line_no);
+	rev_hex = is_null_oid(&file->oid) ? "HEAD" : oid_to_hex(rev);
+	query = cgit_fmt("id=%s#%s", rev_hex, anchor);
+	// The path is repository content, so percent-encode it before it lands
+	// raw in the href.
+	if (file->path)
+		strbuf_add_percentencode(&path, file->path, 0);
+	fileurl = cgit_fileurl(ctx.repo->url, "tree", path.buf, query);
+	html("<td class='lineno'><a href='");
+	html(fileurl);
+	htmlf("'>%s</a>", anchor + 1);
+	html("</td>");
+	free(fileurl);
+	strbuf_release(&path);
+}
+
+static void print_row(const char *class,
+		      int old_line_no, char *old_line,
+		      int new_line_no, char *new_line,
+		      int highlight_chars)
 {
 	char *lcs = NULL;
 
+	// The first byte of a line is the marker xdiff put on it, not text.
 	if (old_line)
-		old_line = replace_tabs(old_line + 1);
+		old_line = expand_tabs(old_line + 1);
 	if (new_line)
-		new_line = replace_tabs(new_line + 1);
-	if (individual_chars && old_line && new_line)
+		new_line = expand_tabs(new_line + 1);
+	if (highlight_chars && old_line && new_line)
 		lcs = longest_common_subsequence(old_line, new_line);
 	html("<tr>\n");
 	if (old_line_no > 0) {
-		struct diff_filespec *old_file = cgit_get_current_old_file();
-		char *lineno_str = cgit_fmt("n%d", old_line_no);
-		char *id_str = cgit_fmt("id=%s#%s", is_null_oid(&old_file->oid)?"HEAD":oid_to_hex(old_rev_oid), lineno_str);
-		struct strbuf path = STRBUF_INIT;
-		char *fileurl;
-		// The file path is repository content, so percent-encode it
-		// before it lands raw in the href below.
-		if (old_file->path)
-			strbuf_add_percentencode(&path, old_file->path, 0);
-		fileurl = cgit_fileurl(ctx.repo->url, "tree", path.buf, id_str);
-		html("<td class='lineno'><a href='");
-		html(fileurl);
-		htmlf("'>%s</a>", lineno_str + 1);
-		html("</td>");
+		print_lineno_cell(cgit_get_current_old_file(), old_rev_oid,
+				  old_line_no);
 		htmlf("<td class='%s'>", class);
-		free(fileurl);
-		strbuf_release(&path);
 	} else if (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) {
 		if (lcs)
-			print_part_with_lcs("del", old_line, lcs);
+			print_line_with_lcs("del", old_line, lcs);
 		else
 			html_txt(old_line);
 	}
 
 	html("</td>\n");
 	if (new_line_no > 0) {
-		struct diff_filespec *new_file = cgit_get_current_new_file();
-		char *lineno_str = cgit_fmt("n%d", new_line_no);
-		char *id_str = cgit_fmt("id=%s#%s", is_null_oid(&new_file->oid)?"HEAD":oid_to_hex(new_rev_oid), lineno_str);
-		struct strbuf path = STRBUF_INIT;
-		char *fileurl;
-		// The file path is repository content, so percent-encode it
-		// before it lands raw in the href below.
-		if (new_file->path)
-			strbuf_add_percentencode(&path, new_file->path, 0);
-		fileurl = cgit_fileurl(ctx.repo->url, "tree", path.buf, id_str);
-		html("<td class='lineno'><a href='");
-		html(fileurl);
-		htmlf("'>%s</a>", lineno_str + 1);
-		html("</td>");
+		print_lineno_cell(cgit_get_current_new_file(), new_rev_oid,
+				  new_line_no);
 		htmlf("<td class='%s'>", class);
-		free(fileurl);
-		strbuf_release(&path);
 	} else if (new_line)
 		htmlf("<td class='lineno'></td><td class='%s'>", class);
 	else
 		htmlf("<td class='lineno'></td><td class='%s_dark'>", class);
 	if (new_line) {
 		if (lcs)
-			print_part_with_lcs("add", new_line, lcs);
+			print_line_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);
+	free(lcs);
+	free(new_line);
+	free(old_line);
+}
+
+static void defer_line(struct deferred_line **head,
+		       struct deferred_line **last,
+		       const char *line, int line_no)
+{
+	struct deferred_line *item = xmalloc(sizeof(*item));
+
+	item->line = xstrdup(line);
+	item->line_no = line_no;
+	item->next = NULL;
+	if (*head)
+		(*last)->next = item;
+	else
+		*head = item;
+	*last = item;
+}
+
+/*
+ * print_row frees only what it derives from the line it is handed and never
+ * keeps the pointer itself, so the item can go as soon as its row is written.
+ */
+static void free_deferred(struct deferred_line *item)
+{
+	free(item->line);
+	free(item);
+}
+
+static int count_deferred(struct deferred_line *item)
+{
+	int count = 0;
+
+	while (item) {
+		count += 1;
+		item = item->next;
+	}
+	return count;
 }
 
 static void print_deferred_old_lines(void)
 {
-	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, 0);
-		tmp = iter_old->next;
-		free_deferred(iter_old);
-		iter_old = tmp;
+	struct deferred_line *item = deferred_old;
+	struct deferred_line *next;
+
+	while (item) {
+		print_row("del", item->line_no, item->line, -1, NULL, 0);
+		next = item->next;
+		free_deferred(item);
+		item = next;
 	}
 }
 
 static void print_deferred_new_lines(void)
 {
-	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, 0);
-		tmp = iter_new->next;
-		free_deferred(iter_new);
-		iter_new = tmp;
+	struct deferred_line *item = deferred_new;
+	struct deferred_line *next;
+
+	while (item) {
+		print_row("add", -1, NULL, item->line_no, item->line, 0);
+		next = item->next;
+		free_deferred(item);
+		item = next;
 	}
 }
 
+/*
+ * Pairing a removal with an addition only stands for anything when the two
+ * runs are the same length, which is why the character marking is offered only
+ * then.
+ */
 static void print_deferred_changed_lines(void)
 {
-	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;
-	while (iter_old || iter_new) {
-		if (iter_old && iter_new)
-			print_ssdiff_line("changed", iter_old->line_no,
-					  iter_old->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, 0);
-		else if (iter_new)
-			print_ssdiff_line("changed", -1, NULL,
-					  iter_new->line_no, iter_new->line, 0);
-		if (iter_old) {
-			tmp = iter_old->next;
-			free_deferred(iter_old);
-			iter_old = tmp;
+	struct deferred_line *old_item = deferred_old;
+	struct deferred_line *new_item = deferred_new;
+	struct deferred_line *next;
+	int highlight_chars;
+
+	highlight_chars = count_deferred(old_item) == count_deferred(new_item);
+	while (old_item || new_item) {
+		if (old_item && new_item)
+			print_row("changed", old_item->line_no,
+				  old_item->line, new_item->line_no,
+				  new_item->line, highlight_chars);
+		else if (old_item)
+			print_row("changed", old_item->line_no,
+				  old_item->line, -1, NULL, 0);
+		else if (new_item)
+			print_row("changed", -1, NULL,
+				  new_item->line_no, new_item->line, 0);
+		if (old_item) {
+			next = old_item->next;
+			free_deferred(old_item);
+			old_item = next;
 		}
 
-		if (iter_new) {
-			tmp = iter_new->next;
-			free_deferred(iter_new);
-			iter_new = tmp;
+		if (new_item) {
+			next = new_item->next;
+			free_deferred(new_item);
+			new_item = next;
 		}
 	}
 }
 
-void cgit_ssdiff_print_deferred_lines(void)
+/*
+ * git leaves the length out when a hunk covers a single line, as in
+ * "@@ -1 +1 @@", so the number runs to whatever follows it rather than to a
+ * comma that may belong to the other side or be missing altogether.
+ */
+static int hunk_start_line(const char *hunk, char marker)
+{
+	const char *p;
+	long line_no;
+
+	p = strchr(hunk, marker);
+	if (p == NULL)
+		return 0;
+	p += 1;
+	line_no = strtol(p, NULL, 10);
+	if (line_no < 0 || line_no > INT_MAX)
+		return 0;
+	return (int)line_no;
+}
+
+static void print_deferred_lines(void)
 {
 	if (!deferred_old && !deferred_new)
 		return;
@@ -382,29 +382,34 @@ void cgit_ssdiff_print_deferred_lines(void)
 }
 
 /*
- * print a single line returned from xdiff
+ * The length counts the byte that ends the line, and the buffer belongs to the
+ * caller, so that byte is only swapped for a NUL while the row is written and
+ * is put back before returning.
  */
 void cgit_ssdiff_line_cb(char *line, int len)
 {
-	char c = line[len - 1];
+	char terminator = line[len - 1];
+
 	line[len - 1] = '\0';
 	if (line[0] == '@') {
-		current_old_line = line_from_hunk(line, '-');
-		current_new_line = line_from_hunk(line, '+');
+		current_old_line = hunk_start_line(line, '-');
+		current_new_line = hunk_start_line(line, '+');
 	}
 
 	if (line[0] == ' ') {
 		if (deferred_old || deferred_new)
-			cgit_ssdiff_print_deferred_lines();
-		print_ssdiff_line("ctx", current_old_line, line,
-				  current_new_line, line, 0);
+			print_deferred_lines();
+		print_row("ctx", current_old_line, line,
+			  current_new_line, line, 0);
 		current_old_line += 1;
 		current_new_line += 1;
 	} else if (line[0] == '+') {
-		deferred_new_add(line, current_new_line);
+		defer_line(&deferred_new, &deferred_new_last, line,
+			   current_new_line);
 		current_new_line += 1;
 	} else if (line[0] == '-') {
-		deferred_old_add(line, current_old_line);
+		defer_line(&deferred_old, &deferred_old_last, line,
+			   current_old_line);
 		current_old_line += 1;
 	} else if (line[0] == '@') {
 		html("<tr><td colspan='4' class='hunk'>");
@@ -415,7 +420,7 @@ void cgit_ssdiff_line_cb(char *line, int len)
 		html_txt(line);
 		html("</td></tr>");
 	}
-	line[len - 1] = c;
+	line[len - 1] = terminator;
 }
 
 void cgit_ssdiff_header_begin(void)
@@ -434,6 +439,6 @@ void cgit_ssdiff_header_end(void)
 void cgit_ssdiff_footer(void)
 {
 	if (deferred_old || deferred_new)
-		cgit_ssdiff_print_deferred_lines();
+		print_deferred_lines();
 	html("<tr><td class='foot' colspan='4'></td></tr>");
 }