revert(3p/git): Revert merge of git upstream at v2.26.2 r/852

This causes cgit to serve error pages, which is undesirable.

This reverts commit 5229c9b232de5bfa959ad6ebbb4c8192ac513352, reversing
changes made to f2b211131f2347342dde63975b09cf603149f1a3.

1 files changed, 279 insertions, 385 deletions

diff --git a/third_party/git/graph.c b/third_party/git/graph.c
index 4fb25ad464db..f53135485f56 100644
--- a/third_party/git/graph.c
+++ b/third_party/git/graph.c
@@ -34,7 +34,6 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb);
  * handle directly. It is assumed that this is the same file handle as the
  * file specified by the graph diff options. This is necessary so that
  * graph_show_strbuf can be called even with a NULL graph.
- * If a NULL graph is supplied, the strbuf is printed as-is.
  */
 static void graph_show_strbuf(struct git_graph *graph,
 			      FILE *file,
@@ -113,42 +112,14 @@ static const char *column_get_color_code(unsigned short color)
 	return column_colors[color];
 }
 
-struct graph_line {
-	struct strbuf *buf;
-	size_t width;
-};
-
-static inline void graph_line_addch(struct graph_line *line, int c)
-{
-	strbuf_addch(line->buf, c);
-	line->width++;
-}
-
-static inline void graph_line_addchars(struct graph_line *line, int c, size_t n)
-{
-	strbuf_addchars(line->buf, c, n);
-	line->width += n;
-}
-
-static inline void graph_line_addstr(struct graph_line *line, const char *s)
-{
-	strbuf_addstr(line->buf, s);
-	line->width += strlen(s);
-}
-
-static inline void graph_line_addcolor(struct graph_line *line, unsigned short color)
-{
-	strbuf_addstr(line->buf, column_get_color_code(color));
-}
-
-static void graph_line_write_column(struct graph_line *line, const struct column *c,
-				    char col_char)
+static void strbuf_write_column(struct strbuf *sb, const struct column *c,
+				char col_char)
 {
 	if (c->color < column_colors_max)
-		graph_line_addcolor(line, c->color);
-	graph_line_addch(line, col_char);
+		strbuf_addstr(sb, column_get_color_code(c->color));
+	strbuf_addch(sb, col_char);
 	if (c->color < column_colors_max)
-		graph_line_addcolor(line, column_colors_max);
+		strbuf_addstr(sb, column_get_color_code(column_colors_max));
 }
 
 struct git_graph {
@@ -204,63 +175,9 @@ struct git_graph {
 	 */
 	int prev_commit_index;
 	/*
-	 * Which layout variant to use to display merge commits. If the
-	 * commit's first parent is known to be in a column to the left of the
-	 * merge, then this value is 0 and we use the layout on the left.
-	 * Otherwise, the value is 1 and the layout on the right is used. This
-	 * field tells us how many columns the first parent occupies.
-	 *
-	 * 		0)			1)
-	 *
-	 * 		| | | *-.		| | *---.
-	 * 		| |_|/|\ \		| | |\ \ \
-	 * 		|/| | | | |		| | | | | *
-	 */
-	int merge_layout;
-	/*
-	 * The number of columns added to the graph by the current commit. For
-	 * 2-way and octopus merges, this is usually one less than the
-	 * number of parents:
-	 *
-	 * 		| | |			| |    \
-	 *		| * |			| *---. \
-	 *		| |\ \			| |\ \ \ \
-	 *		| | | |         	| | | | | |
-	 *
-	 *		num_parents: 2		num_parents: 4
-	 *		edges_added: 1		edges_added: 3
-	 *
-	 * For left-skewed merges, the first parent fuses with its neighbor and
-	 * so one less column is added:
-	 *
-	 *		| | |			| |  \
-	 *		| * |			| *-. \
-	 *		|/| |			|/|\ \ \
-	 *		| | |			| | | | |
-	 *
-	 *		num_parents: 2		num_parents: 4
-	 *		edges_added: 0		edges_added: 2
-	 *
-	 * This number determines how edges to the right of the merge are
-	 * displayed in commit and post-merge lines; if no columns have been
-	 * added then a vertical line should be used where a right-tracking
-	 * line would otherwise be used.
-	 *
-	 *		| * \			| * |
-	 *		| |\ \			|/| |
-	 *		| | * \			| * |
-	 */
-	int edges_added;
-	/*
-	 * The number of columns added by the previous commit, which is used to
-	 * smooth edges appearing to the right of a commit in a commit line
-	 * following a post-merge line.
-	 */
-	int prev_edges_added;
-	/*
 	 * The maximum number of columns that can be stored in the columns
 	 * and new_columns arrays.  This is also half the number of entries
-	 * that can be stored in the mapping and old_mapping arrays.
+	 * that can be stored in the mapping and new_mapping arrays.
 	 */
 	int column_capacity;
 	/*
@@ -298,12 +215,12 @@ struct git_graph {
 	 */
 	int *mapping;
 	/*
-	 * A copy of the contents of the mapping array from the last commit,
-	 * which we use to improve the display of columns that are tracking
-	 * from right to left through a commit line.  We also use this to
-	 * avoid allocating a fresh array when we compute the next mapping.
+	 * A temporary array for computing the next mapping state
+	 * while we are outputting a mapping line.  This is stored as part
+	 * of the git_graph simply so we don't have to allocate a new
+	 * temporary array each time we have to output a collapsing line.
 	 */
-	int *old_mapping;
+	int *new_mapping;
 	/*
 	 * The current default column color being used.  This is
 	 * stored as an index into the array column_colors.
@@ -368,9 +285,6 @@ struct git_graph *graph_init(struct rev_info *opt)
 	graph->prev_state = GRAPH_PADDING;
 	graph->commit_index = 0;
 	graph->prev_commit_index = 0;
-	graph->merge_layout = 0;
-	graph->edges_added = 0;
-	graph->prev_edges_added = 0;
 	graph->num_columns = 0;
 	graph->num_new_columns = 0;
 	graph->mapping_size = 0;
@@ -389,7 +303,7 @@ struct git_graph *graph_init(struct rev_info *opt)
 	ALLOC_ARRAY(graph->columns, graph->column_capacity);
 	ALLOC_ARRAY(graph->new_columns, graph->column_capacity);
 	ALLOC_ARRAY(graph->mapping, 2 * graph->column_capacity);
-	ALLOC_ARRAY(graph->old_mapping, 2 * graph->column_capacity);
+	ALLOC_ARRAY(graph->new_mapping, 2 * graph->column_capacity);
 
 	/*
 	 * The diff output prefix callback, with this we can make
@@ -419,7 +333,7 @@ static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
 	REALLOC_ARRAY(graph->columns, graph->column_capacity);
 	REALLOC_ARRAY(graph->new_columns, graph->column_capacity);
 	REALLOC_ARRAY(graph->mapping, graph->column_capacity * 2);
-	REALLOC_ARRAY(graph->old_mapping, graph->column_capacity * 2);
+	REALLOC_ARRAY(graph->new_mapping, graph->column_capacity * 2);
 }
 
 /*
@@ -518,76 +432,74 @@ static unsigned short graph_find_commit_color(const struct git_graph *graph,
 	return graph_get_current_column_color(graph);
 }
 
-static int graph_find_new_column_by_commit(struct git_graph *graph,
-					   struct commit *commit)
-{
-	int i;
-	for (i = 0; i < graph->num_new_columns; i++) {
-		if (graph->new_columns[i].commit == commit)
-			return i;
-	}
-	return -1;
-}
-
 static void graph_insert_into_new_columns(struct git_graph *graph,
 					  struct commit *commit,
-					  int idx)
+					  int *mapping_index)
 {
-	int i = graph_find_new_column_by_commit(graph, commit);
-	int mapping_idx;
+	int i;
 
 	/*
-	 * If the commit is not already in the new_columns array, then add it
-	 * and record it as being in the final column.
+	 * If the commit is already in the new_columns list, we don't need to
+	 * add it.  Just update the mapping correctly.
 	 */
-	if (i < 0) {
-		i = graph->num_new_columns++;
-		graph->new_columns[i].commit = commit;
-		graph->new_columns[i].color = graph_find_commit_color(graph, commit);
+	for (i = 0; i < graph->num_new_columns; i++) {
+		if (graph->new_columns[i].commit == commit) {
+			graph->mapping[*mapping_index] = i;
+			*mapping_index += 2;
+			return;
+		}
 	}
 
-	if (graph->num_parents > 1 && idx > -1 && graph->merge_layout == -1) {
-		/*
-		 * If this is the first parent of a merge, choose a layout for
-		 * the merge line based on whether the parent appears in a
-		 * column to the left of the merge
-		 */
-		int dist, shift;
-
-		dist = idx - i;
-		shift = (dist > 1) ? 2 * dist - 3 : 1;
+	/*
+	 * This commit isn't already in new_columns.  Add it.
+	 */
+	graph->new_columns[graph->num_new_columns].commit = commit;
+	graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit);
+	graph->mapping[*mapping_index] = graph->num_new_columns;
+	*mapping_index += 2;
+	graph->num_new_columns++;
+}
 
-		graph->merge_layout = (dist > 0) ? 0 : 1;
-		graph->edges_added = graph->num_parents + graph->merge_layout  - 2;
+static void graph_update_width(struct git_graph *graph,
+			       int is_commit_in_existing_columns)
+{
+	/*
+	 * Compute the width needed to display the graph for this commit.
+	 * This is the maximum width needed for any row.  All other rows
+	 * will be padded to this width.
+	 *
+	 * Compute the number of columns in the widest row:
+	 * Count each existing column (graph->num_columns), and each new
+	 * column added by this commit.
+	 */
+	int max_cols = graph->num_columns + graph->num_parents;
 
-		mapping_idx = graph->width + (graph->merge_layout - 1) * shift;
-		graph->width += 2 * graph->merge_layout;
+	/*
+	 * Even if the current commit has no parents to be printed, it
+	 * still takes up a column for itself.
+	 */
+	if (graph->num_parents < 1)
+		max_cols++;
 
-	} else if (graph->edges_added > 0 && i == graph->mapping[graph->width - 2]) {
-		/*
-		 * If some columns have been added by a merge, but this commit
-		 * was found in the last existing column, then adjust the
-		 * numbers so that the two edges immediately join, i.e.:
-		 *
-		 *		* |		* |
-		 *		|\ \	=>	|\|
-		 *		| |/		| *
-		 *		| *
-		 */
-		mapping_idx = graph->width - 2;
-		graph->edges_added = -1;
-	} else {
-		mapping_idx = graph->width;
-		graph->width += 2;
-	}
+	/*
+	 * We added a column for the current commit as part of
+	 * graph->num_parents.  If the current commit was already in
+	 * graph->columns, then we have double counted it.
+	 */
+	if (is_commit_in_existing_columns)
+		max_cols--;
 
-	graph->mapping[mapping_idx] = i;
+	/*
+	 * Each column takes up 2 spaces
+	 */
+	graph->width = max_cols * 2;
 }
 
 static void graph_update_columns(struct git_graph *graph)
 {
 	struct commit_list *parent;
 	int max_new_columns;
+	int mapping_idx;
 	int i, seen_this, is_commit_in_columns;
 
 	/*
@@ -620,10 +532,6 @@ static void graph_update_columns(struct git_graph *graph)
 	for (i = 0; i < graph->mapping_size; i++)
 		graph->mapping[i] = -1;
 
-	graph->width = 0;
-	graph->prev_edges_added = graph->edges_added;
-	graph->edges_added = 0;
-
 	/*
 	 * Populate graph->new_columns and graph->mapping
 	 *
@@ -634,6 +542,7 @@ static void graph_update_columns(struct git_graph *graph)
 	 * supposed to end up after the collapsing is performed.
 	 */
 	seen_this = 0;
+	mapping_idx = 0;
 	is_commit_in_columns = 1;
 	for (i = 0; i <= graph->num_columns; i++) {
 		struct commit *col_commit;
@@ -647,9 +556,9 @@ static void graph_update_columns(struct git_graph *graph)
 		}
 
 		if (col_commit == graph->commit) {
+			int old_mapping_idx = mapping_idx;
 			seen_this = 1;
 			graph->commit_index = i;
-			graph->merge_layout = -1;
 			for (parent = first_interesting_parent(graph);
 			     parent;
 			     parent = next_interesting_parent(graph, parent)) {
@@ -662,18 +571,21 @@ static void graph_update_columns(struct git_graph *graph)
 				    !is_commit_in_columns) {
 					graph_increment_column_color(graph);
 				}
-				graph_insert_into_new_columns(graph, parent->item, i);
+				graph_insert_into_new_columns(graph,
+							      parent->item,
+							      &mapping_idx);
 			}
 			/*
-			 * We always need to increment graph->width by at
+			 * We always need to increment mapping_idx by at
 			 * least 2, even if it has no interesting parents.
 			 * The current commit always takes up at least 2
 			 * spaces.
 			 */
-			if (graph->num_parents == 0)
-				graph->width += 2;
+			if (mapping_idx == old_mapping_idx)
+				mapping_idx += 2;
 		} else {
-			graph_insert_into_new_columns(graph, col_commit, -1);
+			graph_insert_into_new_columns(graph, col_commit,
+						      &mapping_idx);
 		}
 	}
 
@@ -683,43 +595,11 @@ static void graph_update_columns(struct git_graph *graph)
 	while (graph->mapping_size > 1 &&
 	       graph->mapping[graph->mapping_size - 1] < 0)
 		graph->mapping_size--;
-}
-
-static int graph_num_dashed_parents(struct git_graph *graph)
-{
-	return graph->num_parents + graph->merge_layout - 3;
-}
 
-static int graph_num_expansion_rows(struct git_graph *graph)
-{
 	/*
-	 * Normally, we need two expansion rows for each dashed parent line from
-	 * an octopus merge:
-	 *
-	 * 		| *
-	 * 		| |\
-	 * 		| | \
-	 * 		| |  \
-	 * 		| *-. \
-	 * 		| |\ \ \
-	 *
-	 * If the merge is skewed to the left, then its parents occupy one less
-	 * column, and we don't need as many expansion rows to route around it;
-	 * in some cases that means we don't need any expansion rows at all:
-	 *
-	 * 		| *
-	 * 		| |\
-	 * 		| * \
-	 * 		|/|\ \
+	 * Compute graph->width for this commit
 	 */
-	return graph_num_dashed_parents(graph) * 2;
-}
-
-static int graph_needs_pre_commit_line(struct git_graph *graph)
-{
-	return graph->num_parents >= 3 &&
-	       graph->commit_index < (graph->num_columns - 1) &&
-	       graph->expansion_row < graph_num_expansion_rows(graph);
+	graph_update_width(graph, is_commit_in_columns);
 }
 
 void graph_update(struct git_graph *graph, struct commit *commit)
@@ -777,7 +657,8 @@ void graph_update(struct git_graph *graph, struct commit *commit)
 	 */
 	if (graph->state != GRAPH_PADDING)
 		graph->state = GRAPH_SKIP;
-	else if (graph_needs_pre_commit_line(graph))
+	else if (graph->num_parents >= 3 &&
+		 graph->commit_index < (graph->num_columns - 1))
 		graph->state = GRAPH_PRE_COMMIT;
 	else
 		graph->state = GRAPH_COMMIT;
@@ -805,7 +686,8 @@ static int graph_is_mapping_correct(struct git_graph *graph)
 	return 1;
 }
 
-static void graph_pad_horizontally(struct git_graph *graph, struct graph_line *line)
+static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
+				   int chars_written)
 {
 	/*
 	 * Add additional spaces to the end of the strbuf, so that all
@@ -814,22 +696,34 @@ static void graph_pad_horizontally(struct git_graph *graph, struct graph_line *l
 	 * This way, fields printed to the right of the graph will remain
 	 * aligned for the entire commit.
 	 */
-	if (line->width < graph->width)
-		graph_line_addchars(line, ' ', graph->width - line->width);
+	if (chars_written < graph->width)
+		strbuf_addchars(sb, ' ', graph->width - chars_written);
 }
 
 static void graph_output_padding_line(struct git_graph *graph,
-				      struct graph_line *line)
+				      struct strbuf *sb)
 {
 	int i;
 
 	/*
+	 * We could conceivable be called with a NULL commit
+	 * if our caller has a bug, and invokes graph_next_line()
+	 * immediately after graph_init(), without first calling
+	 * graph_update().  Return without outputting anything in this
+	 * case.
+	 */
+	if (!graph->commit)
+		return;
+
+	/*
 	 * Output a padding row, that leaves all branch lines unchanged
 	 */
 	for (i = 0; i < graph->num_new_columns; i++) {
-		graph_line_write_column(line, &graph->new_columns[i], '|');
-		graph_line_addch(line, ' ');
+		strbuf_write_column(sb, &graph->new_columns[i], '|');
+		strbuf_addch(sb, ' ');
 	}
+
+	graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
 }
 
 
@@ -839,24 +733,28 @@ int graph_width(struct git_graph *graph)
 }
 
 
-static void graph_output_skip_line(struct git_graph *graph, struct graph_line *line)
+static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
 {
 	/*
 	 * Output an ellipsis to indicate that a portion
 	 * of the graph is missing.
 	 */
-	graph_line_addstr(line, "...");
+	strbuf_addstr(sb, "...");
+	graph_pad_horizontally(graph, sb, 3);
 
-	if (graph_needs_pre_commit_line(graph))
+	if (graph->num_parents >= 3 &&
+	    graph->commit_index < (graph->num_columns - 1))
 		graph_update_state(graph, GRAPH_PRE_COMMIT);
 	else
 		graph_update_state(graph, GRAPH_COMMIT);
 }
 
 static void graph_output_pre_commit_line(struct git_graph *graph,
-					 struct graph_line *line)
+					 struct strbuf *sb)
 {
+	int num_expansion_rows;
 	int i, seen_this;
+	int chars_written;
 
 	/*
 	 * This function formats a row that increases the space around a commit
@@ -866,24 +764,27 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 	 * We need 2 extra rows for every parent over 2.
 	 */
 	assert(graph->num_parents >= 3);
+	num_expansion_rows = (graph->num_parents - 2) * 2;
 
 	/*
 	 * graph->expansion_row tracks the current expansion row we are on.
 	 * It should be in the range [0, num_expansion_rows - 1]
 	 */
 	assert(0 <= graph->expansion_row &&
-	       graph->expansion_row < graph_num_expansion_rows(graph));
+	       graph->expansion_row < num_expansion_rows);
 
 	/*
 	 * Output the row
 	 */
 	seen_this = 0;
+	chars_written = 0;
 	for (i = 0; i < graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		if (col->commit == graph->commit) {
 			seen_this = 1;
-			graph_line_write_column(line, col, '|');
-			graph_line_addchars(line, ' ', graph->expansion_row);
+			strbuf_write_column(sb, col, '|');
+			strbuf_addchars(sb, ' ', graph->expansion_row);
+			chars_written += 1 + graph->expansion_row;
 		} else if (seen_this && (graph->expansion_row == 0)) {
 			/*
 			 * This is the first line of the pre-commit output.
@@ -896,27 +797,33 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				graph_line_write_column(line, col, '\\');
+				strbuf_write_column(sb, col, '\\');
 			else
-				graph_line_write_column(line, col, '|');
+				strbuf_write_column(sb, col, '|');
+			chars_written++;
 		} else if (seen_this && (graph->expansion_row > 0)) {
-			graph_line_write_column(line, col, '\\');
+			strbuf_write_column(sb, col, '\\');
+			chars_written++;
 		} else {
-			graph_line_write_column(line, col, '|');
+			strbuf_write_column(sb, col, '|');
+			chars_written++;
 		}
-		graph_line_addch(line, ' ');
+		strbuf_addch(sb, ' ');
+		chars_written++;
 	}
 
+	graph_pad_horizontally(graph, sb, chars_written);
+
 	/*
 	 * Increment graph->expansion_row,
 	 * and move to state GRAPH_COMMIT if necessary
 	 */
 	graph->expansion_row++;
-	if (!graph_needs_pre_commit_line(graph))
+	if (graph->expansion_row >= num_expansion_rows)
 		graph_update_state(graph, GRAPH_COMMIT);
 }
 
-static void graph_output_commit_char(struct git_graph *graph, struct graph_line *line)
+static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 {
 	/*
 	 * For boundary commits, print 'o'
@@ -924,67 +831,72 @@ static void graph_output_commit_char(struct git_graph *graph, struct graph_line
 	 */
 	if (graph->commit->object.flags & BOUNDARY) {
 		assert(graph->revs->boundary);
-		graph_line_addch(line, 'o');
+		strbuf_addch(sb, 'o');
 		return;
 	}
 
 	/*
 	 * get_revision_mark() handles all other cases without assert()
 	 */
-	graph_line_addstr(line, get_revision_mark(graph->revs, graph->commit));
+	strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
 }
 
 /*
- * Draw the horizontal dashes of an octopus merge.
+ * Draw the horizontal dashes of an octopus merge and return the number of
+ * characters written.
  */
-static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line *line)
+static int graph_draw_octopus_merge(struct git_graph *graph,
+				    struct strbuf *sb)
 {
 	/*
-	 * The parents of a merge commit can be arbitrarily reordered as they
-	 * are mapped onto display columns, for example this is a valid merge:
+	 * Here dashless_parents represents the number of parents which don't
+	 * need to have dashes (the edges labeled "0" and "1").  And
+	 * dashful_parents are the remaining ones.
 	 *
-	 *	| | *---.
-	 *	| | |\ \ \
-	 *	| | |/ / /
-	 *	| |/| | /
-	 *	| |_|_|/
-	 *	|/| | |
-	 *	3 1 0 2
+	 * | *---.
+	 * | |\ \ \
+	 * | | | | |
+	 * x 0 1 2 3
 	 *
-	 * The numbers denote which parent of the merge each visual column
-	 * corresponds to; we can't assume that the parents will initially
-	 * display in the order given by new_columns.
+	 */
+	const int dashless_parents = 2;
+	int dashful_parents = graph->num_parents - dashless_parents;
+
+	/*
+	 * Usually, we add one new column for each parent (like the diagram
+	 * above) but sometimes the first parent goes into an existing column,
+	 * like this:
 	 *
-	 * To find the right color for each dash, we need to consult the
-	 * mapping array, starting from the column 2 places to the right of the
-	 * merge commit, and use that to find out which logical column each
-	 * edge will collapse to.
+	 * | *---.
+	 * | |\ \ \
+	 * |/ / / /
+	 * x 0 1 2
 	 *
-	 * Commits are rendered once all edges have collapsed to their correct
-	 * logcial column, so commit_index gives us the right visual offset for
-	 * the merge commit.
+	 * In which case the number of parents will be one greater than the
+	 * number of added columns.
 	 */
+	int added_cols = (graph->num_new_columns - graph->num_columns);
+	int parent_in_old_cols = graph->num_parents - added_cols;
 
-	int i, j;
-	struct column *col;
-
-	int dashed_parents = graph_num_dashed_parents(graph);
-
-	for (i = 0; i < dashed_parents; i++) {
-		j = graph->mapping[(graph->commit_index + i + 2) * 2];
-		col = &graph->new_columns[j];
+	/*
+	 * In both cases, commit_index corresponds to the edge labeled "0".
+	 */
+	int first_col = graph->commit_index + dashless_parents
+	    - parent_in_old_cols;
 
-		graph_line_write_column(line, col, '-');
-		graph_line_write_column(line, col, (i == dashed_parents - 1) ? '.' : '-');
+	int i;
+	for (i = 0; i < dashful_parents; i++) {
+		strbuf_write_column(sb, &graph->new_columns[i+first_col], '-');
+		strbuf_write_column(sb, &graph->new_columns[i+first_col],
+				    i == dashful_parents-1 ? '.' : '-');
 	}
-
-	return;
+	return 2 * dashful_parents;
 }
 
-static void graph_output_commit_line(struct git_graph *graph, struct graph_line *line)
+static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
-	int i;
+	int i, chars_written;
 
 	/*
 	 * Output the row containing this commit
@@ -994,6 +906,7 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 	 * children that we have already processed.)
 	 */
 	seen_this = 0;
+	chars_written = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
@@ -1007,17 +920,19 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 
 		if (col_commit == graph->commit) {
 			seen_this = 1;
-			graph_output_commit_char(graph, line);
+			graph_output_commit_char(graph, sb);
+			chars_written++;
 
 			if (graph->num_parents > 2)
-				graph_draw_octopus_merge(graph, line);
-		} else if (seen_this && (graph->edges_added > 1)) {
-			graph_line_write_column(line, col, '\\');
-		} else if (seen_this && (graph->edges_added == 1)) {
+				chars_written += graph_draw_octopus_merge(graph,
+									  sb);
+		} else if (seen_this && (graph->num_parents > 2)) {
+			strbuf_write_column(sb, col, '\\');
+			chars_written++;
+		} else if (seen_this && (graph->num_parents == 2)) {
 			/*
-			 * This is either a right-skewed 2-way merge
-			 * commit, or a left-skewed 3-way merge.
-			 * There is no GRAPH_PRE_COMMIT stage for such
+			 * This is a 2-way merge commit.
+			 * There is no GRAPH_PRE_COMMIT stage for 2-way
 			 * merges, so this is the first line of output
 			 * for this commit.  Check to see what the previous
 			 * line of output was.
@@ -1029,21 +944,21 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 			 * makes the output look nicer.
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
-			    graph->prev_edges_added > 0 &&
 			    graph->prev_commit_index < i)
-				graph_line_write_column(line, col, '\\');
+				strbuf_write_column(sb, col, '\\');
 			else
-				graph_line_write_column(line, col, '|');
-		} else if (graph->prev_state == GRAPH_COLLAPSING &&
-			   graph->old_mapping[2 * i + 1] == i &&
-			   graph->mapping[2 * i] < i) {
-			graph_line_write_column(line, col, '/');
+				strbuf_write_column(sb, col, '|');
+			chars_written++;
 		} else {
-			graph_line_write_column(line, col, '|');
+			strbuf_write_column(sb, col, '|');
+			chars_written++;
 		}
-		graph_line_addch(line, ' ');
+		strbuf_addch(sb, ' ');
+		chars_written++;
 	}
 
+	graph_pad_horizontally(graph, sb, chars_written);
+
 	/*
 	 * Update graph->state
 	 */
@@ -1055,19 +970,26 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
-const char merge_chars[] = {'/', '|', '\\'};
+static struct column *find_new_column_by_commit(struct git_graph *graph,
+						struct commit *commit)
+{
+	int i;
+	for (i = 0; i < graph->num_new_columns; i++) {
+		if (graph->new_columns[i].commit == commit)
+			return &graph->new_columns[i];
+	}
+	return NULL;
+}
 
-static void graph_output_post_merge_line(struct git_graph *graph, struct graph_line *line)
+static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
-	int i, j;
-
-	struct commit_list *first_parent = first_interesting_parent(graph);
-	struct column *parent_col = NULL;
+	int i, j, chars_written;
 
 	/*
 	 * Output the post-merge row
 	 */
+	chars_written = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
@@ -1086,50 +1008,38 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 			 * new_columns and use those to format the
 			 * edges.
 			 */
-			struct commit_list *parents = first_parent;
-			int par_column;
-			int idx = graph->merge_layout;
-			char c;
+			struct commit_list *parents = NULL;
+			struct column *par_column;
 			seen_this = 1;
-
-			for (j = 0; j < graph->num_parents; j++) {
-				par_column = graph_find_new_column_by_commit(graph, parents->item);
-				assert(par_column >= 0);
-
-				c = merge_chars[idx];
-				graph_line_write_column(line, &graph->new_columns[par_column], c);
-				if (idx == 2) {
-					if (graph->edges_added > 0 || j < graph->num_parents - 1)
-						graph_line_addch(line, ' ');
-				} else {
-					idx++;
-				}
+			parents = first_interesting_parent(graph);
+			assert(parents);
+			par_column = find_new_column_by_commit(graph, parents->item);
+			assert(par_column);
+
+			strbuf_write_column(sb, par_column, '|');
+			chars_written++;
+			for (j = 0; j < graph->num_parents - 1; j++) {
 				parents = next_interesting_parent(graph, parents);
+				assert(parents);
+				par_column = find_new_column_by_commit(graph, parents->item);
+				assert(par_column);
+				strbuf_write_column(sb, par_column, '\\');
+				strbuf_addch(sb, ' ');
 			}
-			if (graph->edges_added == 0)
-				graph_line_addch(line, ' ');
-
+			chars_written += j * 2;
 		} else if (seen_this) {
-			if (graph->edges_added > 0)
-				graph_line_write_column(line, col, '\\');
-			else
-				graph_line_write_column(line, col, '|');
-			graph_line_addch(line, ' ');
+			strbuf_write_column(sb, col, '\\');
+			strbuf_addch(sb, ' ');
+			chars_written += 2;
 		} else {
-			graph_line_write_column(line, col, '|');
-			if (graph->merge_layout != 0 || i != graph->commit_index - 1) {
-				if (parent_col)
-					graph_line_write_column(
-						line, parent_col, '_');
-				else
-					graph_line_addch(line, ' ');
-			}
+			strbuf_write_column(sb, col, '|');
+			strbuf_addch(sb, ' ');
+			chars_written += 2;
 		}
-
-		if (col_commit == first_parent->item)
-			parent_col = col;
 	}
 
+	graph_pad_horizontally(graph, sb, chars_written);
+
 	/*
 	 * Update graph->state
 	 */
@@ -1139,7 +1049,7 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
-static void graph_output_collapsing_line(struct git_graph *graph, struct graph_line *line)
+static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int i;
 	short used_horizontal = 0;
@@ -1147,18 +1057,13 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 	int horizontal_edge_target = -1;
 
 	/*
-	 * Swap the mapping and old_mapping arrays
-	 */
-	SWAP(graph->mapping, graph->old_mapping);
-
-	/*
-	 * Clear out the mapping array
+	 * Clear out the new_mapping array
 	 */
 	for (i = 0; i < graph->mapping_size; i++)
-		graph->mapping[i] = -1;
+		graph->new_mapping[i] = -1;
 
 	for (i = 0; i < graph->mapping_size; i++) {
-		int target = graph->old_mapping[i];
+		int target = graph->mapping[i];
 		if (target < 0)
 			continue;
 
@@ -1179,14 +1084,14 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 			 * This column is already in the
 			 * correct place
 			 */
-			assert(graph->mapping[i] == -1);
-			graph->mapping[i] = target;
-		} else if (graph->mapping[i - 1] < 0) {
+			assert(graph->new_mapping[i] == -1);
+			graph->new_mapping[i] = target;
+		} else if (graph->new_mapping[i - 1] < 0) {
 			/*
 			 * Nothing is to the left.
 			 * Move to the left by one
 			 */
-			graph->mapping[i - 1] = target;
+			graph->new_mapping[i - 1] = target;
 			/*
 			 * If there isn't already an edge moving horizontally
 			 * select this one.
@@ -1202,9 +1107,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 				 * line.
 				 */
 				for (j = (target * 2)+3; j < (i - 2); j += 2)
-					graph->mapping[j] = target;
+					graph->new_mapping[j] = target;
 			}
-		} else if (graph->mapping[i - 1] == target) {
+		} else if (graph->new_mapping[i - 1] == target) {
 			/*
 			 * There is a branch line to our left
 			 * already, and it is our target.  We
@@ -1212,7 +1117,7 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 			 * the same parent commit.
 			 *
 			 * We don't have to add anything to the
-			 * output or mapping, since the
+			 * output or new_mapping, since the
 			 * existing branch line has already taken
 			 * care of it.
 			 */
@@ -1224,46 +1129,39 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 			 *
 			 * The space just to the left of this
 			 * branch should always be empty.
+			 *
+			 * The branch to the left of that space
+			 * should be our eventual target.
 			 */
-			assert(graph->mapping[i - 1] > target);
-			assert(graph->mapping[i - 2] < 0);
-			graph->mapping[i - 2] = target;
+			assert(graph->new_mapping[i - 1] > target);
+			assert(graph->new_mapping[i - 2] < 0);
+			assert(graph->new_mapping[i - 3] == target);
+			graph->new_mapping[i - 2] = target;
 			/*
 			 * Mark this branch as the horizontal edge to
 			 * prevent any other edges from moving
 			 * horizontally.
 			 */
-			if (horizontal_edge == -1) {
-				int j;
-				horizontal_edge_target = target;
-				horizontal_edge = i - 1;
-
-				for (j = (target * 2) + 3; j < (i - 2); j += 2)
-					graph->mapping[j] = target;
-			}
+			if (horizontal_edge == -1)
+				horizontal_edge = i;
 		}
 	}
 
 	/*
-	 * Copy the current mapping array into old_mapping
-	 */
-	COPY_ARRAY(graph->old_mapping, graph->mapping, graph->mapping_size);
-
-	/*
 	 * The new mapping may be 1 smaller than the old mapping
 	 */
-	if (graph->mapping[graph->mapping_size - 1] < 0)
+	if (graph->new_mapping[graph->mapping_size - 1] < 0)
 		graph->mapping_size--;
 
 	/*
 	 * Output out a line based on the new mapping info
 	 */
 	for (i = 0; i < graph->mapping_size; i++) {
-		int target = graph->mapping[i];
+		int target = graph->new_mapping[i];
 		if (target < 0)
-			graph_line_addch(line, ' ');
+			strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
-			graph_line_write_column(line, &graph->new_columns[target], '|');
+			strbuf_write_column(sb, &graph->new_columns[target], '|');
 		else if (target == horizontal_edge_target &&
 			 i != horizontal_edge - 1) {
 				/*
@@ -1272,17 +1170,24 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 				 * won't continue into the next line.
 				 */
 				if (i != (target * 2)+3)
-					graph->mapping[i] = -1;
+					graph->new_mapping[i] = -1;
 				used_horizontal = 1;
-			graph_line_write_column(line, &graph->new_columns[target], '_');
+			strbuf_write_column(sb, &graph->new_columns[target], '_');
 		} else {
 			if (used_horizontal && i < horizontal_edge)
-				graph->mapping[i] = -1;
-			graph_line_write_column(line, &graph->new_columns[target], '/');
+				graph->new_mapping[i] = -1;
+			strbuf_write_column(sb, &graph->new_columns[target], '/');
 
 		}
 	}
 
+	graph_pad_horizontally(graph, sb, graph->mapping_size);
+
+	/*
+	 * Swap mapping and new_mapping
+	 */
+	SWAP(graph->mapping, graph->new_mapping);
+
 	/*
 	 * If graph->mapping indicates that all of the branch lines
 	 * are already in the correct positions, we are done.
@@ -1294,49 +1199,35 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 
 int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 {
-	int shown_commit_line = 0;
-	struct graph_line line = { .buf = sb, .width = 0 };
-
-	/*
-	 * We could conceivable be called with a NULL commit
-	 * if our caller has a bug, and invokes graph_next_line()
-	 * immediately after graph_init(), without first calling
-	 * graph_update().  Return without outputting anything in this
-	 * case.
-	 */
-	if (!graph->commit)
-		return -1;
-
 	switch (graph->state) {
 	case GRAPH_PADDING:
-		graph_output_padding_line(graph, &line);
-		break;
+		graph_output_padding_line(graph, sb);
+		return 0;
 	case GRAPH_SKIP:
-		graph_output_skip_line(graph, &line);
-		break;
+		graph_output_skip_line(graph, sb);
+		return 0;
 	case GRAPH_PRE_COMMIT:
-		graph_output_pre_commit_line(graph, &line);
-		break;
+		graph_output_pre_commit_line(graph, sb);
+		return 0;
 	case GRAPH_COMMIT:
-		graph_output_commit_line(graph, &line);
-		shown_commit_line = 1;
-		break;
+		graph_output_commit_line(graph, sb);
+		return 1;
 	case GRAPH_POST_MERGE:
-		graph_output_post_merge_line(graph, &line);
-		break;
+		graph_output_post_merge_line(graph, sb);
+		return 0;
 	case GRAPH_COLLAPSING:
-		graph_output_collapsing_line(graph, &line);
-		break;
+		graph_output_collapsing_line(graph, sb);
+		return 0;
 	}
 
-	graph_pad_horizontally(graph, &line);
-	return shown_commit_line;
+	assert(0);
+	return 0;
 }
 
 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int i;
-	struct graph_line line = { .buf = sb, .width = 0 };
+	int chars_written = 0;
 
 	if (graph->state != GRAPH_COMMIT) {
 		graph_next_line(graph, sb);
@@ -1353,17 +1244,20 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 	for (i = 0; i < graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 
-		graph_line_write_column(&line, col, '|');
+		strbuf_write_column(sb, col, '|');
+		chars_written++;
 
 		if (col->commit == graph->commit && graph->num_parents > 2) {
 			int len = (graph->num_parents - 2) * 2;
-			graph_line_addchars(&line, ' ', len);
+			strbuf_addchars(sb, ' ', len);
+			chars_written += len;
 		} else {
-			graph_line_addch(&line, ' ');
+			strbuf_addch(sb, ' ');
+			chars_written++;
 		}
 	}
 
-	graph_pad_horizontally(graph, &line);
+	graph_pad_horizontally(graph, sb, chars_written);
 
 	/*
 	 * Update graph->prev_state since we have output a padding line