Emit generated runs in batches, not a write each

5 files changed, 162 insertions, 60 deletions

diff --git a/source/html.h b/source/html.h
index fa4de77..7572623 100644
--- a/source/html.h
+++ b/source/html.h
@@ -6,6 +6,13 @@
 extern void html_raw(const char *txt, size_t size);
 extern void html(const char *txt);
 
+/* How much of a generated run to build before handing it to html_raw. Batching
+ * is what removes the write per line, and html_raw already gathers what it is
+ * given into one buffer, so nothing is gained by growing past this. A run built
+ * whole would instead be sized by the file it was generated from, which the
+ * blob limits do not bound. */
+#define HTML_BATCH (64 * 1024)
+
 __attribute__((format (printf,1,2)))
 extern void htmlf(const char *format,...);
 
diff --git a/source/ui-blame.c b/source/ui-blame.c
index 418e3ae..d6779c0 100644
--- a/source/ui-blame.c
+++ b/source/ui-blame.c
@@ -16,6 +16,38 @@
 #include "blame.h"
 
 
+/* Blame coalesces neighbouring lines from one commit, but a commit that
+ * touched several separate parts of the file still comes back once per part.
+ * Each of those repeats a full commit parse, so the rendered detail is kept
+ * and looked up by object id. */
+static struct string_list suspect_details = STRING_LIST_INIT_DUP;
+
+static void free_suspect_details(void)
+{
+	struct string_list_item *item;
+
+	for_each_string_list_item(item, &suspect_details)
+		free(item->util);
+	string_list_clear(&suspect_details, 0);
+}
+
+/* Write out a run of one repeated character. A single blame entry can cover
+ * the whole file, so the run is handed on in batches rather than built whole. */
+static void emit_chars(char ch, unsigned long count)
+{
+	struct strbuf run = STRBUF_INIT;
+
+	while (count) {
+		unsigned long n = count < HTML_BATCH ? count : HTML_BATCH;
+
+		strbuf_addchars(&run, ch, n);
+		html_raw(run.buf, run.len);
+		strbuf_reset(&run);
+		count -= n;
+	}
+	strbuf_release(&run);
+}
+
 static char *emit_suspect_detail(struct blame_origin *suspect)
 {
 	struct commitinfo *info;
@@ -47,7 +79,6 @@ static void emit_blame_entry_hash(struct blame_entry *ent)
 {
 	struct blame_origin *suspect = ent->suspect;
 	struct object_id *oid = &suspect->commit->object.oid;
-	unsigned long line = 0;
 
 	char *detail = emit_suspect_detail(suspect);
 	html("<span class='oid'>");
@@ -65,28 +96,36 @@ static void emit_blame_entry_hash(struct blame_entry *ent)
 				suspect->path);
 	}
 
-	while (line++ < ent->num_lines)
-		html("\n");
+	// Batched rather than one write per line of the entry.
+	emit_chars('\n', ent->num_lines);
 }
 
 static void emit_blame_entry_linenumber(struct blame_entry *ent)
 {
 	const char *numberfmt = "<a id='n%1$d' href='#n%1$d'>%1$d</a>\n";
+	struct strbuf numbers = STRBUF_INIT;
+	int lineno = ent->lno;
 
-	unsigned long lineno = ent->lno;
-	while (lineno < ent->lno + ent->num_lines)
-		htmlf(numberfmt, ++lineno);
+	// Batched rather than a formatted write per line of the entry.
+	while (lineno < ent->lno + ent->num_lines) {
+		strbuf_addf(&numbers, numberfmt, ++lineno);
+		if (numbers.len >= HTML_BATCH) {
+			html_raw(numbers.buf, numbers.len);
+			strbuf_reset(&numbers);
+		}
+	}
+	html_raw(numbers.buf, numbers.len);
+	strbuf_release(&numbers);
 }
 
 static void emit_blame_entry_line_background(struct blame_scoreboard *sb,
 					     struct blame_entry *ent)
 {
-	unsigned long line;
+	int line;
 	size_t len, maxlen = 2;
 	const char* pos, *endpos;
 
 	for (line = ent->lno; line < ent->lno + ent->num_lines; line++) {
-		html("\n");
 		pos = blame_nth_line(sb, line);
 		endpos = blame_nth_line(sb, line + 1);
 		len = 0;
@@ -99,8 +138,11 @@ static void emit_blame_entry_line_background(struct blame_scoreboard *sb,
 			maxlen = len;
 	}
 
-	for (len = 0; len < maxlen - 1; len++)
-		html(" ");
+	// The widest line decides the padding, so the entry has to be measured
+	// before any of it is written. The newlines do not depend on that
+	// measurement, so both runs go out batched once it is known.
+	emit_chars('\n', ent->num_lines);
+	emit_chars(' ', maxlen - 1);
 }
 
 struct walk_tree_context {
diff --git a/source/ui-ssdiff.c b/source/ui-ssdiff.c
index 7cea09e..e4472c4 100644
--- a/source/ui-ssdiff.c
+++ b/source/ui-ssdiff.c
@@ -18,14 +18,20 @@ struct deferred_lines {
 static struct deferred_lines *deferred_old, *deferred_old_last;
 static struct deferred_lines *deferred_new, *deferred_new_last;
 
-static void create_or_reset_lcs_table(void)
+/*
+ * 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.
+ */
+static void create_lcs_table(void)
 {
 	int i;
 
-	if (L != NULL) {
-		memset(*L, 0, sizeof(int) * MAX_SSDIFF_SIZE);
+	if (L != NULL)
 		return;
-	}
 
 	// xcalloc will die if we ran out of memory;
 	// not very helpful for debugging
@@ -50,7 +56,7 @@ static char *longest_common_subsequence(char *A, char *B)
 	if (m >= MAX_SSDIFF_M || n >= MAX_SSDIFF_N)
 		return NULL;
 
-	create_or_reset_lcs_table();
+	create_lcs_table();
 
 	for (i = m; i >= 0; i--) {
 		for (j = n; j >= 0; j--) {
@@ -110,44 +116,20 @@ static int line_from_hunk(char *line, char type)
 
 static char *replace_tabs(char *line)
 {
-	char *prev_buf = line;
-	char *cur_buf;
-	size_t linelen = strlen(line);
-	int n_tabs = 0;
-	int i;
-	char *result;
-	size_t result_len;
-
-	if (linelen == 0) {
-		result = xmalloc(1);
-		result[0] = '\0';
-		return result;
-	}
+	struct strbuf out = STRBUF_INIT;
+	const char *p;
 
-	for (i = 0; i < linelen; i++) {
-		if (line[i] == '\t')
-			n_tabs += 1;
-	}
-	result_len = linelen + n_tabs * 8;
-	result = xmalloc(result_len + 1);
-	result[0] = '\0';
-
-	for (;;) {
-		cur_buf = strchr(prev_buf, '\t');
-		if (!cur_buf) {
-			linelen = strlen(result);
-			strlcpy(&result[linelen], prev_buf, result_len - linelen + 1);
-			break;
-		} else {
-			linelen = strlen(result);
-			strlcpy(&result[linelen], prev_buf, cur_buf - prev_buf + 1);
-			linelen = strlen(result);
-			memset(&result[linelen], ' ', 8 - (linelen % 8));
-			result[linelen + 8 - (linelen % 8)] = '\0';
-		}
-		prev_buf = cur_buf + 1;
+	// 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));
+		else
+			strbuf_addch(&out, *p);
 	}
-	return result;
+	return strbuf_detach(&out, NULL);
 }
 
 static int calc_deferred_lines(struct deferred_lines *start)
@@ -210,28 +192,35 @@ static void print_part_with_lcs(const char *class, char *line, char *lcs)
 {
 	int line_len = strlen(line);
 	int i, j;
-	char c[2] = " ";
 	int same = 1;
+	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++) {
-		c[0] = line[i];
 		if (same) {
 			if (line[i] == lcs[j])
 				j += 1;
 			else {
 				same = 0;
+				flush_run(&run);
 				htmlf("<span class='%s'>", class);
 			}
 		} else if (line[i] == lcs[j]) {
 			same = 1;
+			flush_run(&run);
 			html("</span>");
 			j += 1;
 		}
-		html_txt(c);
+		strbuf_addch(&run, line[i]);
 	}
+	flush_run(&run);
 	if (!same)
 		html("</span>");
+	strbuf_release(&run);
 }
 
 static void print_ssdiff_line(const char *class,
diff --git a/source/ui-tree.c b/source/ui-tree.c
index bc5986b..64be0b6 100644
--- a/source/ui-tree.c
+++ b/source/ui-tree.c
@@ -38,18 +38,31 @@ static void print_text_buffer(const char *name, char *buf, unsigned long size)
 	html("<table summary='blob content' class='blob'>\n");
 
 	if (ctx.cfg.enable_tree_linenumbers) {
+		struct strbuf numbers = STRBUF_INIT;
+
 		html("<tr><td class='linenumbers'><pre>");
 		idx = 0;
 		lineno = 0;
 
+		// Build the column in batches. A formatted write per line meant
+		// a syscall and a temporary buffer for every line of the file,
+		// which is most of what rendering a large blob cost, and the
+		// whole column at once would come to several times the blob.
 		if (size) {
-			htmlf(numberfmt, ++lineno);
+			strbuf_addf(&numbers, numberfmt, ++lineno);
 			while (idx < size - 1) { // skip absolute last newline
-				if (buf[idx] == '\n')
-					htmlf(numberfmt, ++lineno);
+				if (buf[idx] == '\n') {
+					strbuf_addf(&numbers, numberfmt, ++lineno);
+					if (numbers.len >= HTML_BATCH) {
+						html_raw(numbers.buf, numbers.len);
+						strbuf_reset(&numbers);
+					}
+				}
 				idx++;
 			}
+			html_raw(numbers.buf, numbers.len);
 		}
+		strbuf_release(&numbers);
 		html("</pre></td>\n");
 	}
 	else {
@@ -75,8 +88,6 @@ static void print_text_buffer(const char *name, char *buf, unsigned long size)
 	html("</code></pre></td></tr></table>\n");
 }
 
-#define ROWLEN 32
-
 static void print_binary_buffer(char *buf, unsigned long size)
 {
 	unsigned long ofs, idx;
@@ -105,6 +116,7 @@ static void print_binary_buffer(char *buf, unsigned long size)
 		html_txt(ascii);
 		html("</td></tr>\n");
 	}
+	strbuf_release(&row);
 	html("</table>\n");
 }
 
@@ -393,7 +405,6 @@ static void ls_tree(const struct object_id *oid, const char *path, struct walk_t
 	ls_tail();
 }
 
-
 static int walk_tree(const struct object_id *oid, struct strbuf *base,
 		const char *pathname, unsigned mode, void *cbdata)
 {
diff --git a/tests/t0106-diff.sh b/tests/t0106-diff.sh
index 3e0d15c..4074276 100755
--- a/tests/t0106-diff.sh
+++ b/tests/t0106-diff.sh
@@ -51,4 +51,57 @@ test_expect_success 'ssdiff still numbers a hunk that carries a length' '
 	grep "#n1.>1</a>" tmp
 '
 
+# --- Intra-line highlighting across many changed pairs ----------------------
+# The character-level highlight reuses one table across every changed pair.
+# Lines shrink down the file so a short comparison always follows a longer one,
+# which is where a stale cell would show up as misplaced del and add spans.
+test_expect_success 'set up a repo with shrinking changed lines' '
+	mkrepo repos/lcs 1 &&
+	(
+		cd repos/lcs &&
+		awk "BEGIN{for(n=120;n>0;n-=3){s=\"\";
+			for(i=0;i<n;i++)s=s sprintf(\"%c\",97+(i*7+n)%26); print s}}" >lines.txt &&
+		git add lines.txt &&
+		git commit -m "add lines.txt" &&
+		awk "BEGIN{for(n=120;n>0;n-=3){s=\"\";
+			for(i=0;i<n;i++){c=97+(i*7+n)%26; if(i%7==0)c=97+(c-97+5)%26;
+			s=s sprintf(\"%c\",c)} print s}}" >lines.txt &&
+		git commit -am "change every line"
+	) &&
+	{
+		echo "virtual-root=/" &&
+		echo "cache-size=0" &&
+		echo "repo.url=lcs" &&
+		echo "repo.path=$PWD/repos/lcs/.git"
+	} >lcsrc
+'
+
+test_expect_success 'every changed pair gets both a del and an add span' '
+	CGIT_CONFIG="$PWD/lcsrc" QUERY_STRING="url=lcs/diff/&dt=1" cgit >tmp &&
+	dels=$(grep -o "<span class=.del.>" tmp | wc -l) &&
+	adds=$(grep -o "<span class=.add.>" tmp | wc -l) &&
+	test "$dels" -gt 0 &&
+	test "$dels" -eq "$adds"
+'
+
+test_expect_success 'stripping the highlight leaves every line intact' '
+	sed -e "s/<[^>]*>//g" tmp >plain.out &&
+	git -C repos/lcs show HEAD~1:lines.txt >old.txt &&
+	git -C repos/lcs show HEAD:lines.txt >new.txt &&
+	while read -r line
+	do
+		grep -qF "$line" plain.out || {
+			echo "missing old line: $line"
+			return 1
+		}
+	done <old.txt &&
+	while read -r line
+	do
+		grep -qF "$line" plain.out || {
+			echo "missing new line: $line"
+			return 1
+		}
+	done <new.txt
+'
+
 test_done