diff options
context:
space:
mode:
Diffstat (limited to 'source/ui-ssdiff.c')
-rw-r--r--source/ui-ssdiff.c497
1 file changed, 251 insertions, 246 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;
+ int old_len = strlen(old_line);
+ int new_len = strlen(new_line);
+ int i, j, pos, lcs_len;
+ char *lcs;
- // We bail if the lines are too long
- if (m >= MAX_SSDIFF_M || n >= MAX_SSDIFF_N)
+ 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);
+ struct deferred_line *old_item = deferred_old;
+ struct deferred_line *new_item = deferred_new;
+ struct deferred_line *next;
+ int highlight_chars;
- 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;
+ 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>");
}
Copyright © 2026 Bryce Kwon. All Rights Deprecated.