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 longest old line and the longest new line the view will compare
// character by character. The comparison fills a cell for every pair of
// characters, so its cost is the product of the two, and a line past the limit
// is shown whole instead.
#define MAX_SSDIFF_M 128
#define MAX_SSDIFF_N 128
#define MAX_SSDIFF_SIZE (MAX_SSDIFF_M * MAX_SSDIFF_N)

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

// The pair being rendered, whose two sides the line number links lead into.
static struct diff_filepair *current_filepair;
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.
 */
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++;
			i++;
			j++;
		} else if (lcs_table[i + 1][j] >= lcs_table[i][j + 1]) {
			i++;
		} else {
			j++;
		}
	}

	return lcs;
}

/*
 * The line with its tabs expanded, which the caller owns. Built in one
 * forward pass so a tab heavy line stays linear 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 the other side does not share is escaped in one call, so a
 * changed line does not go through the output path a byte at a time.
 */
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++;
			} 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++;
		}
		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 so that the url
	// stays a url whatever bytes the path holds.
	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);
}

/*
 * mark is the class for the characters this side of the row does not share
 * with the other.
 */
static void print_side(const char *class, struct diff_filespec *file, const struct object_id *rev,
	int line_no, const char *line, const char *lcs, const char *mark)
{
	if (line_no > 0)
		print_lineno_cell(file, rev, line_no);
	else
		html("<td class='lineno'></td>");
	htmlf("<td class='%s%s'>", class, line ? "" : "-dark");
	if (line) {
		if (lcs)
			print_line_with_lcs(mark, line, lcs);
		else
			html_txt(line);
	}
	html("</td>");
}

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");
	print_side(class, current_filepair->one, old_rev_oid, old_line_no, old_line, lcs, "del");
	html("\n");
	print_side(class, current_filepair->two, new_rev_oid, new_line_no, new_line, lcs, "add");
	html("</tr>\n");
	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++;
		item = item->next;
	}
	return count;
}

/*
 * 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_run(const char *class)
{
	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(class, old_item->line_no, old_item->line,
				new_item->line_no, new_item->line, highlight_chars);
		else if (old_item)
			print_row(class, old_item->line_no, old_item->line, -1, NULL, 0);
		else if (new_item)
			print_row(class, -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)
		return 0;
	p++;
	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;
	print_deferred_run(!deferred_new ? "del" : !deferred_old ? "add" : "changed");
	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] == ' ') {
		print_deferred_lines();
		print_row("ctx", current_old_line, line, current_new_line, line, 0);
		current_old_line++;
		current_new_line++;
	} else if (line[0] == '+') {
		defer_line(&deferred_new, &deferred_new_last, line, current_new_line);
		current_new_line++;
	} else if (line[0] == '-') {
		defer_line(&deferred_old, &deferred_old_last, line, current_old_line);
		current_old_line++;
	} else if (line[0] == '@') {
		html("<tr><td colspan='4' class='hunk'>");
		html_txt(line);
		html("</td></tr>\n");
	} else {
		html("<tr><td colspan='4' class='ctx'>");
		html_txt(line);
		html("</td></tr>\n");
	}
	line[len - 1] = terminator;
}

void cgit_ssdiff_header_begin(struct diff_filepair *pair)
{
	current_filepair = pair;
	current_old_line = -1;
	current_new_line = -1;
	html("<tbody class='file' data-path='");
	html_attr(pair->two->path);
	html("'>\n");
	html("<tr><td class='space' colspan='4'></td></tr>\n");
	html("<tr><td class='head' colspan='4'>");
}

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

void cgit_ssdiff_footer(void)
{
	print_deferred_lines();
	html("<tr><td class='foot' colspan='4'></td></tr>\n</tbody>\n");
}