index : cgit

/*
 * 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 "html.h"
#include "ui-diff.h"
#include "ui-shared.h"
#include "ui-ssdiff.h"

// 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

// One line held back until its run ends, owning the copy taken of it.
struct deferred_line {
	int line_no;
	char *line;
	struct deferred_line *next;
};

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 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 (lcs_table)
		return;

	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;
}

/*
 * 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 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 = 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 {
				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_len = lcs_table[0][0];
	lcs = xmalloc(lcs_len + 2);
	memset(lcs, 0, sizeof(*lcs) * (lcs_len + 2));

	pos = 0;
	i = 0;
	j = 0;
	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 (lcs_table[i + 1][j] >= lcs_table[i][j + 1]) {
			i += 1;
		} else {
			j += 1;
		}
	}

	return lcs;
}

/*
 * 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;

	for (p = line; *p; p++) {
		if (*p == '\t')
			strbuf_addchars(&out, ' ',
					TAB_WIDTH - (out.len % TAB_WIDTH));
		else
			strbuf_addch(&out, *p);
	}
	return strbuf_detach(&out, NULL);
}

static void flush_run(struct strbuf *run)
{
	if (!run->len)
		return;
	html_txt(run->buf);
	strbuf_reset(run);
}

/*
 * 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 len = strlen(line);
	int in_common = 1;
	int matched = 0;
	int i;
	struct strbuf run = STRBUF_INIT;

	for (i = 0; i < len; i++) {
		if (in_common) {
			if (line[i] == lcs[matched])
				matched += 1;
			else {
				in_common = 0;
				flush_run(&run);
				htmlf("<span class='%s'>", class);
			}
		} else if (line[i] == lcs[matched]) {
			in_common = 1;
			flush_run(&run);
			html("</span>");
			matched += 1;
		}
		strbuf_addch(&run, line[i]);
	}
	flush_run(&run);
	if (!in_common)
		html("</span>");
	strbuf_release(&run);
}

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_attr(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 = expand_tabs(old_line + 1);
	if (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) {
		print_lineno_cell(cgit_get_current_old_file(), old_rev_oid,
				  old_line_no);
		htmlf("<td class='%s'>", class);
	} 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_line_with_lcs("del", old_line, lcs);
		else
			html_txt(old_line);
	}

	html("</td>\n");
	if (new_line_no > 0) {
		print_lineno_cell(cgit_get_current_new_file(), new_rev_oid,
				  new_line_no);
		htmlf("<td class='%s'>", class);
	} 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_line_with_lcs("add", new_line, lcs);
		else
			html_txt(new_line);
	}

	html("</td></tr>");
	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_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_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_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 (new_item) {
			next = new_item->next;
			free_deferred(new_item);
			new_item = next;
		}
	}
}

/*
 * 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;
	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;
}

/*
 * 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 terminator = line[len - 1];

	line[len - 1] = '\0';
	if (line[0] == '@') {
		current_old_line = hunk_start_line(line, '-');
		current_new_line = hunk_start_line(line, '+');
	}

	if (line[0] == ' ') {
		if (deferred_old || deferred_new)
			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] == '+') {
		defer_line(&deferred_new, &deferred_new_last, line,
			   current_new_line);
		current_new_line += 1;
	} else if (line[0] == '-') {
		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'>");
		html_txt(line);
		html("</td></tr>");
	} else {
		html("<tr><td colspan='4' class='ctx'>");
		html_txt(line);
		html("</td></tr>");
	}
	line[len - 1] = terminator;
}

void cgit_ssdiff_header_begin(void)
{
	current_old_line = -1;
	current_new_line = -1;
	html("<tr><td class='space' colspan='4'><div></div></td></tr>");
	html("<tr><td class='head' colspan='4'>");
}

void cgit_ssdiff_header_end(void)
{
	html("</td></tr>");
}

void cgit_ssdiff_footer(void)
{
	if (deferred_old || deferred_new)
		print_deferred_lines();
	html("<tr><td class='foot' colspan='4'></td></tr>");
}