From fbccf255f9449c2f617d875ebf78b9f1730fae5d Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:47 +0000
Subject: graph: automatically track display width of graph lines

All the output functions called by `graph_next_line()` currently keep
track of how many printable chars they've written to the buffer, before
calling `graph_pad_horizontally()` to pad the line with spaces. Some
functions do this by incrementing a counter whenever they write to the
buffer, and others do it by encoding an assumption about how many chars
are written, as in:

    graph_pad_horizontally(graph, sb, graph->num_columns * 2);

This adds a fair amount of noise to the functions' logic and is easily
broken if one forgets to increment the right counter or update the
calculations used for padding.

To make this easier to use, I'm introducing a new struct called
`graph_line` that wraps a `strbuf` and keeps count of its display width
implicitly. `graph_next_line()` wraps this around the `struct strbuf *`
it's given and passes a `struct graph_line *` to the output functions,
which use its interface.

The `graph_line` interface wraps the `strbuf_addch()`,
`strbuf_addchars()` and `strbuf_addstr()` functions, and adds the
`graph_line_write_column()` function for adding a single character with
color formatting. The `graph_pad_horizontally()` function can then use
the `width` field from the struct rather than taking a character count
as a parameter.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 194 +++++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 99 insertions(+), 95 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index f53135485f..2f81a5d23d 100644
--- a/graph.c
+++ b/graph.c
@@ -112,14 +112,42 @@ static const char *column_get_color_code(unsigned short color)
 	return column_colors[color];
 }
 
-static void strbuf_write_column(struct strbuf *sb, const struct column *c,
-				char col_char)
+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)
 {
 	if (c->color < column_colors_max)
-		strbuf_addstr(sb, column_get_color_code(c->color));
-	strbuf_addch(sb, col_char);
+		graph_line_addcolor(line, c->color);
+	graph_line_addch(line, col_char);
 	if (c->color < column_colors_max)
-		strbuf_addstr(sb, column_get_color_code(column_colors_max));
+		graph_line_addcolor(line, column_colors_max);
 }
 
 struct git_graph {
@@ -686,8 +714,7 @@ static int graph_is_mapping_correct(struct git_graph *graph)
 	return 1;
 }
 
-static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
-				   int chars_written)
+static void graph_pad_horizontally(struct git_graph *graph, struct graph_line *line)
 {
 	/*
 	 * Add additional spaces to the end of the strbuf, so that all
@@ -696,12 +723,12 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
 	 * This way, fields printed to the right of the graph will remain
 	 * aligned for the entire commit.
 	 */
-	if (chars_written < graph->width)
-		strbuf_addchars(sb, ' ', graph->width - chars_written);
+	if (line->width < graph->width)
+		graph_line_addchars(line, ' ', graph->width - line->width);
 }
 
 static void graph_output_padding_line(struct git_graph *graph,
-				      struct strbuf *sb)
+				      struct graph_line *line)
 {
 	int i;
 
@@ -719,11 +746,11 @@ static void graph_output_padding_line(struct git_graph *graph,
 	 * Output a padding row, that leaves all branch lines unchanged
 	 */
 	for (i = 0; i < graph->num_new_columns; i++) {
-		strbuf_write_column(sb, &graph->new_columns[i], '|');
-		strbuf_addch(sb, ' ');
+		graph_line_write_column(line, &graph->new_columns[i], '|');
+		graph_line_addch(line, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
+	graph_pad_horizontally(graph, line);
 }
 
 
@@ -733,14 +760,14 @@ int graph_width(struct git_graph *graph)
 }
 
 
-static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_skip_line(struct git_graph *graph, struct graph_line *line)
 {
 	/*
 	 * Output an ellipsis to indicate that a portion
 	 * of the graph is missing.
 	 */
-	strbuf_addstr(sb, "...");
-	graph_pad_horizontally(graph, sb, 3);
+	graph_line_addstr(line, "...");
+	graph_pad_horizontally(graph, line);
 
 	if (graph->num_parents >= 3 &&
 	    graph->commit_index < (graph->num_columns - 1))
@@ -750,11 +777,10 @@ static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
 }
 
 static void graph_output_pre_commit_line(struct git_graph *graph,
-					 struct strbuf *sb)
+					 struct graph_line *line)
 {
 	int num_expansion_rows;
 	int i, seen_this;
-	int chars_written;
 
 	/*
 	 * This function formats a row that increases the space around a commit
@@ -777,14 +803,12 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 	 * 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;
-			strbuf_write_column(sb, col, '|');
-			strbuf_addchars(sb, ' ', graph->expansion_row);
-			chars_written += 1 + graph->expansion_row;
+			graph_line_write_column(line, col, '|');
+			graph_line_addchars(line, ' ', graph->expansion_row);
 		} else if (seen_this && (graph->expansion_row == 0)) {
 			/*
 			 * This is the first line of the pre-commit output.
@@ -797,22 +821,18 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				strbuf_write_column(sb, col, '\\');
+				graph_line_write_column(line, col, '\\');
 			else
-				strbuf_write_column(sb, col, '|');
-			chars_written++;
+				graph_line_write_column(line, col, '|');
 		} else if (seen_this && (graph->expansion_row > 0)) {
-			strbuf_write_column(sb, col, '\\');
-			chars_written++;
+			graph_line_write_column(line, col, '\\');
 		} else {
-			strbuf_write_column(sb, col, '|');
-			chars_written++;
+			graph_line_write_column(line, col, '|');
 		}
-		strbuf_addch(sb, ' ');
-		chars_written++;
+		graph_line_addch(line, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, line);
 
 	/*
 	 * Increment graph->expansion_row,
@@ -823,7 +843,7 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		graph_update_state(graph, GRAPH_COMMIT);
 }
 
-static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_commit_char(struct git_graph *graph, struct graph_line *line)
 {
 	/*
 	 * For boundary commits, print 'o'
@@ -831,22 +851,20 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 	 */
 	if (graph->commit->object.flags & BOUNDARY) {
 		assert(graph->revs->boundary);
-		strbuf_addch(sb, 'o');
+		graph_line_addch(line, 'o');
 		return;
 	}
 
 	/*
 	 * get_revision_mark() handles all other cases without assert()
 	 */
-	strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
+	graph_line_addstr(line, get_revision_mark(graph->revs, graph->commit));
 }
 
 /*
- * Draw the horizontal dashes of an octopus merge and return the number of
- * characters written.
+ * Draw the horizontal dashes of an octopus merge.
  */
-static int graph_draw_octopus_merge(struct git_graph *graph,
-				    struct strbuf *sb)
+static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line *line)
 {
 	/*
 	 * Here dashless_parents represents the number of parents which don't
@@ -886,17 +904,16 @@ static int graph_draw_octopus_merge(struct git_graph *graph,
 
 	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 ? '.' : '-');
+		graph_line_write_column(line, &graph->new_columns[i+first_col], '-');
+		graph_line_write_column(line, &graph->new_columns[i+first_col],
+					  i == dashful_parents-1 ? '.' : '-');
 	}
-	return 2 * dashful_parents;
 }
 
-static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_commit_line(struct git_graph *graph, struct graph_line *line)
 {
 	int seen_this = 0;
-	int i, chars_written;
+	int i;
 
 	/*
 	 * Output the row containing this commit
@@ -906,7 +923,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 	 * 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;
@@ -920,15 +936,12 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 
 		if (col_commit == graph->commit) {
 			seen_this = 1;
-			graph_output_commit_char(graph, sb);
-			chars_written++;
+			graph_output_commit_char(graph, line);
 
 			if (graph->num_parents > 2)
-				chars_written += graph_draw_octopus_merge(graph,
-									  sb);
+				graph_draw_octopus_merge(graph, line);
 		} else if (seen_this && (graph->num_parents > 2)) {
-			strbuf_write_column(sb, col, '\\');
-			chars_written++;
+			graph_line_write_column(line, col, '\\');
 		} else if (seen_this && (graph->num_parents == 2)) {
 			/*
 			 * This is a 2-way merge commit.
@@ -945,19 +958,16 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				strbuf_write_column(sb, col, '\\');
+				graph_line_write_column(line, col, '\\');
 			else
-				strbuf_write_column(sb, col, '|');
-			chars_written++;
+				graph_line_write_column(line, col, '|');
 		} else {
-			strbuf_write_column(sb, col, '|');
-			chars_written++;
+			graph_line_write_column(line, col, '|');
 		}
-		strbuf_addch(sb, ' ');
-		chars_written++;
+		graph_line_addch(line, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, line);
 
 	/*
 	 * Update graph->state
@@ -981,15 +991,14 @@ static struct column *find_new_column_by_commit(struct git_graph *graph,
 	return NULL;
 }
 
-static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_post_merge_line(struct git_graph *graph, struct graph_line *line)
 {
 	int seen_this = 0;
-	int i, j, chars_written;
+	int i, j;
 
 	/*
 	 * 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;
@@ -1016,29 +1025,25 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 			par_column = find_new_column_by_commit(graph, parents->item);
 			assert(par_column);
 
-			strbuf_write_column(sb, par_column, '|');
-			chars_written++;
+			graph_line_write_column(line, par_column, '|');
 			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, ' ');
+				graph_line_write_column(line, par_column, '\\');
+				graph_line_addch(line, ' ');
 			}
-			chars_written += j * 2;
 		} else if (seen_this) {
-			strbuf_write_column(sb, col, '\\');
-			strbuf_addch(sb, ' ');
-			chars_written += 2;
+			graph_line_write_column(line, col, '\\');
+			graph_line_addch(line, ' ');
 		} else {
-			strbuf_write_column(sb, col, '|');
-			strbuf_addch(sb, ' ');
-			chars_written += 2;
+			graph_line_write_column(line, col, '|');
+			graph_line_addch(line, ' ');
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, line);
 
 	/*
 	 * Update graph->state
@@ -1049,7 +1054,7 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
-static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_collapsing_line(struct git_graph *graph, struct graph_line *line)
 {
 	int i;
 	short used_horizontal = 0;
@@ -1159,9 +1164,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 	for (i = 0; i < graph->mapping_size; i++) {
 		int target = graph->new_mapping[i];
 		if (target < 0)
-			strbuf_addch(sb, ' ');
+			graph_line_addch(line, ' ');
 		else if (target * 2 == i)
-			strbuf_write_column(sb, &graph->new_columns[target], '|');
+			graph_line_write_column(line, &graph->new_columns[target], '|');
 		else if (target == horizontal_edge_target &&
 			 i != horizontal_edge - 1) {
 				/*
@@ -1172,16 +1177,16 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 				if (i != (target * 2)+3)
 					graph->new_mapping[i] = -1;
 				used_horizontal = 1;
-			strbuf_write_column(sb, &graph->new_columns[target], '_');
+			graph_line_write_column(line, &graph->new_columns[target], '_');
 		} else {
 			if (used_horizontal && i < horizontal_edge)
 				graph->new_mapping[i] = -1;
-			strbuf_write_column(sb, &graph->new_columns[target], '/');
+			graph_line_write_column(line, &graph->new_columns[target], '/');
 
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, graph->mapping_size);
+	graph_pad_horizontally(graph, line);
 
 	/*
 	 * Swap mapping and new_mapping
@@ -1199,24 +1204,26 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 
 int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 {
+	struct graph_line line = { .buf = sb, .width = 0 };
+
 	switch (graph->state) {
 	case GRAPH_PADDING:
-		graph_output_padding_line(graph, sb);
+		graph_output_padding_line(graph, &line);
 		return 0;
 	case GRAPH_SKIP:
-		graph_output_skip_line(graph, sb);
+		graph_output_skip_line(graph, &line);
 		return 0;
 	case GRAPH_PRE_COMMIT:
-		graph_output_pre_commit_line(graph, sb);
+		graph_output_pre_commit_line(graph, &line);
 		return 0;
 	case GRAPH_COMMIT:
-		graph_output_commit_line(graph, sb);
+		graph_output_commit_line(graph, &line);
 		return 1;
 	case GRAPH_POST_MERGE:
-		graph_output_post_merge_line(graph, sb);
+		graph_output_post_merge_line(graph, &line);
 		return 0;
 	case GRAPH_COLLAPSING:
-		graph_output_collapsing_line(graph, sb);
+		graph_output_collapsing_line(graph, &line);
 		return 0;
 	}
 
@@ -1227,7 +1234,7 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int i;
-	int chars_written = 0;
+	struct graph_line line = { .buf = sb, .width = 0 };
 
 	if (graph->state != GRAPH_COMMIT) {
 		graph_next_line(graph, sb);
@@ -1244,20 +1251,17 @@ 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];
 
-		strbuf_write_column(sb, col, '|');
-		chars_written++;
+		graph_line_write_column(&line, col, '|');
 
 		if (col->commit == graph->commit && graph->num_parents > 2) {
 			int len = (graph->num_parents - 2) * 2;
-			strbuf_addchars(sb, ' ', len);
-			chars_written += len;
+			graph_line_addchars(&line, ' ', len);
 		} else {
-			strbuf_addch(sb, ' ');
-			chars_written++;
+			graph_line_addch(&line, ' ');
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, &line);
 
 	/*
 	 * Update graph->prev_state since we have output a padding line
-- 
cgit v1.2.3


From 210179a20d585f6a96e0963db69790e590bd9433 Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:48 +0000
Subject: graph: handle line padding in `graph_next_line()`

Now that the display width of graph lines is implicitly tracked via the
`graph_line` interface, the calls to `graph_pad_horizontally()` no
longer need to be located inside the individual output functions, where
the character counting was previously being done.

All the functions called by `graph_next_line()` generate a line of
output, then call `graph_pad_horizontally()`, and finally change the
graph state if necessary. As padding is the final change to the output
done by all these functions, it can be removed from all of them and done
in `graph_next_line()` instead.

I've also moved the guard in `graph_output_padding_line()` that checks
the graph has a commit; this function is only called by
`graph_next_line()` and we must not pad the `graph_line` if no commit is
set.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 49 ++++++++++++++++++++-----------------------------
 1 file changed, 20 insertions(+), 29 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index 2f81a5d23d..4c68557b17 100644
--- a/graph.c
+++ b/graph.c
@@ -732,16 +732,6 @@ static void graph_output_padding_line(struct git_graph *graph,
 {
 	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
 	 */
@@ -749,8 +739,6 @@ static void graph_output_padding_line(struct git_graph *graph,
 		graph_line_write_column(line, &graph->new_columns[i], '|');
 		graph_line_addch(line, ' ');
 	}
-
-	graph_pad_horizontally(graph, line);
 }
 
 
@@ -767,7 +755,6 @@ static void graph_output_skip_line(struct git_graph *graph, struct graph_line *l
 	 * of the graph is missing.
 	 */
 	graph_line_addstr(line, "...");
-	graph_pad_horizontally(graph, line);
 
 	if (graph->num_parents >= 3 &&
 	    graph->commit_index < (graph->num_columns - 1))
@@ -832,8 +819,6 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		graph_line_addch(line, ' ');
 	}
 
-	graph_pad_horizontally(graph, line);
-
 	/*
 	 * Increment graph->expansion_row,
 	 * and move to state GRAPH_COMMIT if necessary
@@ -967,8 +952,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 		graph_line_addch(line, ' ');
 	}
 
-	graph_pad_horizontally(graph, line);
-
 	/*
 	 * Update graph->state
 	 */
@@ -1043,8 +1026,6 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 		}
 	}
 
-	graph_pad_horizontally(graph, line);
-
 	/*
 	 * Update graph->state
 	 */
@@ -1186,8 +1167,6 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 		}
 	}
 
-	graph_pad_horizontally(graph, line);
-
 	/*
 	 * Swap mapping and new_mapping
 	 */
@@ -1204,31 +1183,43 @@ 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);
-		return 0;
+		break;
 	case GRAPH_SKIP:
 		graph_output_skip_line(graph, &line);
-		return 0;
+		break;
 	case GRAPH_PRE_COMMIT:
 		graph_output_pre_commit_line(graph, &line);
-		return 0;
+		break;
 	case GRAPH_COMMIT:
 		graph_output_commit_line(graph, &line);
-		return 1;
+		shown_commit_line = 1;
+		break;
 	case GRAPH_POST_MERGE:
 		graph_output_post_merge_line(graph, &line);
-		return 0;
+		break;
 	case GRAPH_COLLAPSING:
 		graph_output_collapsing_line(graph, &line);
-		return 0;
+		break;
 	}
 
-	assert(0);
-	return 0;
+	graph_pad_horizontally(graph, &line);
+	return shown_commit_line;
 }
 
 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
-- 
cgit v1.2.3


From 9157a2a032c4c5a154782537b6f1e2f8b7bd7435 Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:49 +0000
Subject: graph: reuse `find_new_column_by_commit()`

I will shortly be making some changes to
`graph_insert_into_new_columns()` and so am trying to simplify it. One
possible simplification is that we can extract the loop for finding the
element in `new_columns` containing the given commit.

`find_new_column_by_commit()` contains a very similar loop but it
returns a `struct column *` rather than an `int` offset into the array.
Here I'm introducing a version that returns `int` and using that in
`graph_insert_into_new_columns()` and `graph_output_post_merge_line()`.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 48 +++++++++++++++++++++++-------------------------
 1 file changed, 23 insertions(+), 25 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index 4c68557b17..c9646d9e00 100644
--- a/graph.c
+++ b/graph.c
@@ -460,22 +460,31 @@ 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 *mapping_index)
 {
-	int i;
+	int i = graph_find_new_column_by_commit(graph, commit);
 
 	/*
 	 * If the commit is already in the new_columns list, we don't need to
 	 * add it.  Just update the mapping correctly.
 	 */
-	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 (i >= 0) {
+		graph->mapping[*mapping_index] = i;
+		*mapping_index += 2;
+		return;
 	}
 
 	/*
@@ -963,17 +972,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
-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)
 {
 	int seen_this = 0;
@@ -1001,20 +999,20 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 			 * edges.
 			 */
 			struct commit_list *parents = NULL;
-			struct column *par_column;
+			int par_column;
 			seen_this = 1;
 			parents = first_interesting_parent(graph);
 			assert(parents);
-			par_column = find_new_column_by_commit(graph, parents->item);
-			assert(par_column);
+			par_column = graph_find_new_column_by_commit(graph, parents->item);
+			assert(par_column >= 0);
 
-			graph_line_write_column(line, par_column, '|');
+			graph_line_write_column(line, &graph->new_columns[par_column], '|');
 			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);
-				graph_line_write_column(line, par_column, '\\');
+				par_column = graph_find_new_column_by_commit(graph, parents->item);
+				assert(par_column >= 0);
+				graph_line_write_column(line, &graph->new_columns[par_column], '\\');
 				graph_line_addch(line, ' ');
 			}
 		} else if (seen_this) {
-- 
cgit v1.2.3


From a551fd5efd7b82604c3254e3f7cac08eaaa97ba9 Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:50 +0000
Subject: graph: reduce duplication in `graph_insert_into_new_columns()`

I will shortly be making some changes to this function and so am trying
to simplify it. It currently contains some duplicated logic; both
branches the function can take assign the commit's column index into
the `mapping` array and increment `mapping_index`.

Here I change the function so that the only conditional behaviour is
that it appends the commit to `new_columns` if it's not present. All
manipulation of `mapping` now happens on a single code path.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 20 +++++++-------------
 1 file changed, 7 insertions(+), 13 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index c9646d9e00..512ae16535 100644
--- a/graph.c
+++ b/graph.c
@@ -478,23 +478,17 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 	int i = graph_find_new_column_by_commit(graph, commit);
 
 	/*
-	 * If the commit is already in the new_columns list, we don't need to
-	 * add it.  Just update the mapping correctly.
+	 * If the commit is not already in the new_columns array, then add it
+	 * and record it as being in the final column.
 	 */
-	if (i >= 0) {
-		graph->mapping[*mapping_index] = i;
-		*mapping_index += 2;
-		return;
+	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);
 	}
 
-	/*
-	 * 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;
+	graph->mapping[*mapping_index] = i;
 	*mapping_index += 2;
-	graph->num_new_columns++;
 }
 
 static void graph_update_width(struct git_graph *graph,
-- 
cgit v1.2.3


From 46ba2abdfa95a26a86714dab386a72a3a5b706a5 Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:51 +0000
Subject: graph: remove `mapping_idx` and `graph_update_width()`

There's a duplication of logic between `graph_insert_into_new_columns()`
and `graph_update_width()`. `graph_insert_into_new_columns()` is called
repeatedly by `graph_update_columns()` with an `int *` that tracks the
offset into the `mapping` array where we should write the next value.
Each call to `graph_insert_into_new_columns()` effectively pushes one
column index and one "null" value (-1) onto the `mapping` array and
therefore increments `mapping_idx` by 2.

`graph_update_width()` duplicates this process: the `width` of the graph
is essentially the initial width of the `mapping` array before edges
begin collapsing. The `graph_update_width()` function's logic
effectively works out how many times `graph_insert_into_new_columns()`
was called based on the relationship of the current commit to the rest
of the graph.

I'm about to make some changes that make the assignment of values into
the `mapping` array more complicated. Rather than make
`graph_update_width()` more complicated at the same time, we can simply
remove this function and use `graph->width` to track the offset into the
`mapping` array as we're building it. This removes the duplication and
makes sure that `graph->width` is the same as the visual width of the
`mapping` array once `graph_update_columns()` is complete.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 65 ++++++++++-------------------------------------------------------
 1 file changed, 10 insertions(+), 55 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index 512ae16535..d724ef25c3 100644
--- a/graph.c
+++ b/graph.c
@@ -472,8 +472,7 @@ static int graph_find_new_column_by_commit(struct git_graph *graph,
 }
 
 static void graph_insert_into_new_columns(struct git_graph *graph,
-					  struct commit *commit,
-					  int *mapping_index)
+					  struct commit *commit)
 {
 	int i = graph_find_new_column_by_commit(graph, commit);
 
@@ -487,50 +486,14 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 		graph->new_columns[i].color = graph_find_commit_color(graph, commit);
 	}
 
-	graph->mapping[*mapping_index] = i;
-	*mapping_index += 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;
-
-	/*
-	 * 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++;
-
-	/*
-	 * 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--;
-
-	/*
-	 * Each column takes up 2 spaces
-	 */
-	graph->width = max_cols * 2;
+	graph->mapping[graph->width] = i;
+	graph->width += 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;
 
 	/*
@@ -563,6 +526,8 @@ static void graph_update_columns(struct git_graph *graph)
 	for (i = 0; i < graph->mapping_size; i++)
 		graph->mapping[i] = -1;
 
+	graph->width = 0;
+
 	/*
 	 * Populate graph->new_columns and graph->mapping
 	 *
@@ -573,7 +538,6 @@ 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;
@@ -587,7 +551,6 @@ 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;
 			for (parent = first_interesting_parent(graph);
@@ -602,21 +565,18 @@ 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,
-							      &mapping_idx);
+				graph_insert_into_new_columns(graph, parent->item);
 			}
 			/*
-			 * We always need to increment mapping_idx by at
+			 * We always need to increment graph->width by at
 			 * least 2, even if it has no interesting parents.
 			 * The current commit always takes up at least 2
 			 * spaces.
 			 */
-			if (mapping_idx == old_mapping_idx)
-				mapping_idx += 2;
+			if (graph->num_parents == 0)
+				graph->width += 2;
 		} else {
-			graph_insert_into_new_columns(graph, col_commit,
-						      &mapping_idx);
+			graph_insert_into_new_columns(graph, col_commit);
 		}
 	}
 
@@ -626,11 +586,6 @@ static void graph_update_columns(struct git_graph *graph)
 	while (graph->mapping_size > 1 &&
 	       graph->mapping[graph->mapping_size - 1] < 0)
 		graph->mapping_size--;
-
-	/*
-	 * Compute graph->width for this commit
-	 */
-	graph_update_width(graph, is_commit_in_columns);
 }
 
 void graph_update(struct git_graph *graph, struct commit *commit)
-- 
cgit v1.2.3


From ee7abb5ffaaba8c3fc5f89765609f30d638f63f7 Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:52 +0000
Subject: graph: extract logic for moving to GRAPH_PRE_COMMIT state

This computation is repeated in a couple of places and I need to add
another condition to it to implement a further improvement to the graph
rendering, so I'm extracting this into a function.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index d724ef25c3..bd7403065e 100644
--- a/graph.c
+++ b/graph.c
@@ -588,6 +588,12 @@ static void graph_update_columns(struct git_graph *graph)
 		graph->mapping_size--;
 }
 
+static int graph_needs_pre_commit_line(struct git_graph *graph)
+{
+	return graph->num_parents >= 3 &&
+	       graph->commit_index < (graph->num_columns - 1);
+}
+
 void graph_update(struct git_graph *graph, struct commit *commit)
 {
 	struct commit_list *parent;
@@ -643,8 +649,7 @@ void graph_update(struct git_graph *graph, struct commit *commit)
 	 */
 	if (graph->state != GRAPH_PADDING)
 		graph->state = GRAPH_SKIP;
-	else if (graph->num_parents >= 3 &&
-		 graph->commit_index < (graph->num_columns - 1))
+	else if (graph_needs_pre_commit_line(graph))
 		graph->state = GRAPH_PRE_COMMIT;
 	else
 		graph->state = GRAPH_COMMIT;
@@ -714,8 +719,7 @@ static void graph_output_skip_line(struct git_graph *graph, struct graph_line *l
 	 */
 	graph_line_addstr(line, "...");
 
-	if (graph->num_parents >= 3 &&
-	    graph->commit_index < (graph->num_columns - 1))
+	if (graph_needs_pre_commit_line(graph))
 		graph_update_state(graph, GRAPH_PRE_COMMIT);
 	else
 		graph_update_state(graph, GRAPH_COMMIT);
-- 
cgit v1.2.3


From 0f0f389f12029b1c3745f8ed7aacfe6b2fc7a6cc Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:54 +0000
Subject: graph: tidy up display of left-skewed merges

Currently, when we display a merge whose first parent is already present
in a column to the left of the merge commit, we display the first parent
as a vertical pipe `|` in the GRAPH_POST_MERGE line and then immediately
enter the GRAPH_COLLAPSING state. The first-parent line tracks to the
left and all the other parent lines follow it; this creates a "kink" in
those lines:

        | *---.
        | |\ \ \
        |/ / / /
        | | | *

This change tidies the display of such commits such that if the first
parent appears to the left of the merge, we render it as a `/` and the
second parent as a `|`. This reduces the horizontal and vertical space
needed to render the merge, and makes the resulting lines easier to
read.

        | *-.
        |/|\ \
        | | | *

If the first parent is separated from the merge by several columns, a
horizontal line is drawn in a similar manner to how the GRAPH_COLLAPSING
state displays the line.

        | | | *-.
        | |_|/|\ \
        |/| | | | *

This effect is applied to both "normal" two-parent merges, and to
octopus merges. It also reduces the vertical space needed for pre-commit
lines, as the merge occupies one less column than usual.

        Before:         After:

        | *             | *
        | |\            | |\
        | | \           | * \
        | |  \          |/|\ \
        | *-. \
        | |\ \ \

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 125 +++++++++++++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 97 insertions(+), 28 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index bd7403065e..e37127f5ab 100644
--- a/graph.c
+++ b/graph.c
@@ -202,6 +202,20 @@ struct git_graph {
 	 * previous commit.
 	 */
 	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 maximum number of columns that can be stored in the columns
 	 * and new_columns arrays.  This is also half the number of entries
@@ -313,6 +327,7 @@ 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->num_columns = 0;
 	graph->num_new_columns = 0;
 	graph->mapping_size = 0;
@@ -472,9 +487,11 @@ static int graph_find_new_column_by_commit(struct git_graph *graph,
 }
 
 static void graph_insert_into_new_columns(struct git_graph *graph,
-					  struct commit *commit)
+					  struct commit *commit,
+					  int idx)
 {
 	int i = graph_find_new_column_by_commit(graph, commit);
+	int mapping_idx;
 
 	/*
 	 * If the commit is not already in the new_columns array, then add it
@@ -486,8 +503,26 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 		graph->new_columns[i].color = graph_find_commit_color(graph, commit);
 	}
 
-	graph->mapping[graph->width] = i;
-	graph->width += 2;
+	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;
+
+		graph->merge_layout = (dist > 0) ? 0 : 1;
+		mapping_idx = graph->width + (graph->merge_layout - 1) * shift;
+		graph->width += 2 * graph->merge_layout;
+	} else {
+		mapping_idx = graph->width;
+		graph->width += 2;
+	}
+
+	graph->mapping[mapping_idx] = i;
 }
 
 static void graph_update_columns(struct git_graph *graph)
@@ -553,6 +588,7 @@ static void graph_update_columns(struct git_graph *graph)
 		if (col_commit == graph->commit) {
 			seen_this = 1;
 			graph->commit_index = i;
+			graph->merge_layout = -1;
 			for (parent = first_interesting_parent(graph);
 			     parent;
 			     parent = next_interesting_parent(graph, parent)) {
@@ -565,7 +601,7 @@ 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);
+				graph_insert_into_new_columns(graph, parent->item, i);
 			}
 			/*
 			 * We always need to increment graph->width by at
@@ -576,7 +612,7 @@ static void graph_update_columns(struct git_graph *graph)
 			if (graph->num_parents == 0)
 				graph->width += 2;
 		} else {
-			graph_insert_into_new_columns(graph, col_commit);
+			graph_insert_into_new_columns(graph, col_commit, -1);
 		}
 	}
 
@@ -588,10 +624,36 @@ static void graph_update_columns(struct git_graph *graph)
 		graph->mapping_size--;
 }
 
+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:
+	 *
+	 * 		| *
+	 * 		| |\
+	 * 		| * \
+	 * 		|/|\ \
+	 */
+	return (graph->num_parents + graph->merge_layout - 3) * 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->commit_index < (graph->num_columns - 1) &&
+	       graph->expansion_row < graph_num_expansion_rows(graph);
 }
 
 void graph_update(struct git_graph *graph, struct commit *commit)
@@ -728,7 +790,6 @@ static void graph_output_skip_line(struct git_graph *graph, struct graph_line *l
 static void graph_output_pre_commit_line(struct git_graph *graph,
 					 struct graph_line *line)
 {
-	int num_expansion_rows;
 	int i, seen_this;
 
 	/*
@@ -739,14 +800,13 @@ 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 < num_expansion_rows);
+	       graph->expansion_row < graph_num_expansion_rows(graph));
 
 	/*
 	 * Output the row
@@ -786,7 +846,7 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 	 * and move to state GRAPH_COMMIT if necessary
 	 */
 	graph->expansion_row++;
-	if (graph->expansion_row >= num_expansion_rows)
+	if (!graph_needs_pre_commit_line(graph))
 		graph_update_state(graph, GRAPH_COMMIT);
 }
 
@@ -824,7 +884,7 @@ static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line
 	 * x 0 1 2 3
 	 *
 	 */
-	const int dashless_parents = 2;
+	const int dashless_parents = 3 - graph->merge_layout;
 	int dashful_parents = graph->num_parents - dashless_parents;
 
 	/*
@@ -832,9 +892,9 @@ static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line
 	 * above) but sometimes the first parent goes into an existing column,
 	 * like this:
 	 *
-	 * | *---.
-	 * | |\ \ \
-	 * |/ / / /
+	 * | *-.
+	 * |/|\ \
+	 * | | | |
 	 * x 0 1 2
 	 *
 	 * In which case the number of parents will be one greater than the
@@ -925,10 +985,15 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
+const char merge_chars[] = {'/', '|', '\\'};
+
 static void graph_output_post_merge_line(struct git_graph *graph, struct graph_line *line)
 {
 	int seen_this = 0;
-	int i, j;
+	int i;
+
+	struct commit_list *first_parent = first_interesting_parent(graph);
+	int seen_parent = 0;
 
 	/*
 	 * Output the post-merge row
@@ -951,30 +1016,34 @@ 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 = NULL;
+			struct commit_list *parents = first_parent;
 			int par_column;
+			int idx = graph->merge_layout;
+			char c;
 			seen_this = 1;
-			parents = first_interesting_parent(graph);
-			assert(parents);
-			par_column = graph_find_new_column_by_commit(graph, parents->item);
-			assert(par_column >= 0);
-
-			graph_line_write_column(line, &graph->new_columns[par_column], '|');
-			for (j = 0; j < graph->num_parents - 1; j++) {
-				parents = next_interesting_parent(graph, parents);
-				assert(parents);
+
+			for (; parents; parents = next_interesting_parent(graph, parents)) {
 				par_column = graph_find_new_column_by_commit(graph, parents->item);
 				assert(par_column >= 0);
-				graph_line_write_column(line, &graph->new_columns[par_column], '\\');
-				graph_line_addch(line, ' ');
+
+				c = merge_chars[idx];
+				graph_line_write_column(line, &graph->new_columns[par_column], c);
+				if (idx == 2)
+					graph_line_addch(line, ' ');
+				else
+					idx++;
 			}
 		} else if (seen_this) {
 			graph_line_write_column(line, col, '\\');
 			graph_line_addch(line, ' ');
 		} else {
 			graph_line_write_column(line, col, '|');
-			graph_line_addch(line, ' ');
+			if (graph->merge_layout != 0 || i != graph->commit_index - 1)
+				graph_line_addch(line, seen_parent ? '_' : ' ');
 		}
+
+		if (col_commit == first_parent->item)
+			seen_parent = 1;
 	}
 
 	/*
-- 
cgit v1.2.3


From d62893ecc125767d44a194279bcaffa0d02d2572 Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:55 +0000
Subject: graph: commit and post-merge lines for left-skewed merges

Following the introduction of "left-skewed" merges, which are merges
whose first parent fuses with another edge to its left, we have some
more edge cases to deal with in the display of commit and post-merge
lines.

The current graph code handles the following cases for edges appearing
to the right of the commit (*) on commit lines. A 2-way merge is usually
followed by vertical lines:

        | | |
        | * |
        | |\ \

An octopus merge (more than two parents) is always followed by edges
sloping to the right:

        | |  \          | |    \
        | *-. \         | *---. \
        | |\ \ \        | |\ \ \ \

A 2-way merge is followed by a right-sloping edge if the commit line
immediately follows a post-merge line for a commit that appears in the
same column as the current commit, or any column to the left of that:

        | *             | * |
        | |\            | |\ \
        | * \           | | * \
        | |\ \          | | |\ \

This commit introduces the following new cases for commit lines. If a
2-way merge skews to the left, then the edges to its right are always
vertical lines, even if the commit follows a post-merge line:

        | | |           | |\
        | * |           | * |
        |/| |           |/| |

A commit with 3 parents that skews left is followed by vertical edges:

        | | |
        | * |
        |/|\ \

If a 3-way left-skewed merge commit appears immediately after a
post-merge line, then it may be followed the right-sloping edges, just
like a 2-way merge that is not skewed.

        | |\
        | * \
        |/|\ \

Octopus merges with 4 or more parents that skew to the left will always
be followed by right-sloping edges, because the existing columns need to
expand around the merge.

        | |  \
        | *-. \
        |/|\ \ \

On post-merge lines, usually all edges following the current commit
slope to the right:

        | * | |
        | |\ \ \

However, if the commit is a left-skewed 2-way merge, the edges to its
right remain vertical. We also need to display a space after the
vertical line descending from the commit marker, whereas this line would
normally be followed by a backslash.

        | * | |
        |/| | |

If a left-skewed merge has more than 2 parents, then the edges to its
right are still sloped as they bend around the edges introduced by the
merge.

        | * | |
        |/|\ \ \

To handle these new cases, we need to know not just how many parents
each commit has, but how many new columns it adds to the display; this
quantity is recorded in the `edges_added` field for the current commit,
and `prev_edges_added` field for the previous commit.

Here, "column" refers to visual columns, not the logical columns of the
`columns` array. This is because even if all the commit's parents end up
fusing with existing edges, they initially introduce distinct edges in
the commit and post-merge lines before those edges collapse. For
example, a 3-way merge whose 2nd and 3rd parents fuse with existing
edges still introduces 2 visual columns that affect the display of edges
to their right.

        | | |  \
        | | *-. \
        | | |\ \ \
        | |_|/ / /
        |/| | / /
        | | |/ /
        | |/| |
        | | | |

This merge does not introduce any *logical* columns; there are 4 edges
before and after this commit once all edges have collapsed. But it does
initially introduce 2 new edges that need to be accommodated by the
edges to their right.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 58 insertions(+), 5 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index e37127f5ab..21edad8085 100644
--- a/graph.c
+++ b/graph.c
@@ -216,6 +216,46 @@ struct git_graph {
 	 * 		|/| | | | |		| | | | | *
 	 */
 	int merge_layout;
+	/*
+	 * The number of columns added to the graph by the current commit. For
+	 * 2-way and octopus merges, this is 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
@@ -328,6 +368,8 @@ struct git_graph *graph_init(struct rev_info *opt)
 	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;
@@ -689,6 +731,9 @@ void graph_update(struct git_graph *graph, struct commit *commit)
 	 */
 	graph_update_columns(graph);
 
+	graph->prev_edges_added = graph->edges_added;
+	graph->edges_added = graph->num_parents + graph->merge_layout - 2;
+
 	graph->expansion_row = 0;
 
 	/*
@@ -947,12 +992,13 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 
 			if (graph->num_parents > 2)
 				graph_draw_octopus_merge(graph, line);
-		} else if (seen_this && (graph->num_parents > 2)) {
+		} else if (seen_this && (graph->edges_added > 1)) {
 			graph_line_write_column(line, col, '\\');
-		} else if (seen_this && (graph->num_parents == 2)) {
+		} else if (seen_this && (graph->edges_added == 1)) {
 			/*
-			 * This is a 2-way merge commit.
-			 * There is no GRAPH_PRE_COMMIT stage for 2-way
+			 * 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
 			 * merges, so this is the first line of output
 			 * for this commit.  Check to see what the previous
 			 * line of output was.
@@ -964,6 +1010,7 @@ 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, '\\');
 			else
@@ -1033,8 +1080,14 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 				else
 					idx++;
 			}
+			if (graph->edges_added == 0)
+				graph_line_addch(line, ' ');
+
 		} else if (seen_this) {
-			graph_line_write_column(line, col, '\\');
+			if (graph->edges_added > 0)
+				graph_line_write_column(line, col, '\\');
+			else
+				graph_line_write_column(line, col, '|');
 			graph_line_addch(line, ' ');
 		} else {
 			graph_line_write_column(line, col, '|');
-- 
cgit v1.2.3


From 0195285b956e1b52defa6c259253a7b888fc25df Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:56 +0000
Subject: graph: rename `new_mapping` to `old_mapping`

The change I'm about to make requires being able to inspect the mapping
array that was used to render the last GRAPH_COLLAPSING line while
rendering a GRAPH_COMMIT line. The `new_mapping` array currently exists
as a pre-allocated space for computing the next `mapping` array during
`graph_output_collapsing_line()`, but we can repurpose it to let us see
the previous `mapping` state.

To support this use it will make more sense if this array is named
`old_mapping`, as it will contain the mapping data for the previous line
we rendered, at the point we're rendering a commit line.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 54 +++++++++++++++++++++++++++---------------------------
 1 file changed, 27 insertions(+), 27 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index 21edad8085..2315f3604d 100644
--- a/graph.c
+++ b/graph.c
@@ -259,7 +259,7 @@ struct git_graph {
 	/*
 	 * 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 new_mapping arrays.
+	 * that can be stored in the mapping and old_mapping arrays.
 	 */
 	int column_capacity;
 	/*
@@ -302,7 +302,7 @@ struct git_graph {
 	 * 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 *new_mapping;
+	int *old_mapping;
 	/*
 	 * The current default column color being used.  This is
 	 * stored as an index into the array column_colors.
@@ -388,7 +388,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->new_mapping, 2 * graph->column_capacity);
+	ALLOC_ARRAY(graph->old_mapping, 2 * graph->column_capacity);
 
 	/*
 	 * The diff output prefix callback, with this we can make
@@ -418,7 +418,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->new_mapping, graph->column_capacity * 2);
+	REALLOC_ARRAY(graph->old_mapping, graph->column_capacity * 2);
 }
 
 /*
@@ -1116,13 +1116,18 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 	int horizontal_edge_target = -1;
 
 	/*
-	 * Clear out the new_mapping array
+	 * Swap the mapping and old_mapping arrays
+	 */
+	SWAP(graph->mapping, graph->old_mapping);
+
+	/*
+	 * Clear out the mapping array
 	 */
 	for (i = 0; i < graph->mapping_size; i++)
-		graph->new_mapping[i] = -1;
+		graph->mapping[i] = -1;
 
 	for (i = 0; i < graph->mapping_size; i++) {
-		int target = graph->mapping[i];
+		int target = graph->old_mapping[i];
 		if (target < 0)
 			continue;
 
@@ -1143,14 +1148,14 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 			 * This column is already in the
 			 * correct place
 			 */
-			assert(graph->new_mapping[i] == -1);
-			graph->new_mapping[i] = target;
-		} else if (graph->new_mapping[i - 1] < 0) {
+			assert(graph->mapping[i] == -1);
+			graph->mapping[i] = target;
+		} else if (graph->mapping[i - 1] < 0) {
 			/*
 			 * Nothing is to the left.
 			 * Move to the left by one
 			 */
-			graph->new_mapping[i - 1] = target;
+			graph->mapping[i - 1] = target;
 			/*
 			 * If there isn't already an edge moving horizontally
 			 * select this one.
@@ -1166,9 +1171,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->new_mapping[j] = target;
+					graph->mapping[j] = target;
 			}
-		} else if (graph->new_mapping[i - 1] == target) {
+		} else if (graph->mapping[i - 1] == target) {
 			/*
 			 * There is a branch line to our left
 			 * already, and it is our target.  We
@@ -1176,7 +1181,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 new_mapping, since the
+			 * output or mapping, since the
 			 * existing branch line has already taken
 			 * care of it.
 			 */
@@ -1192,10 +1197,10 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 			 * The branch to the left of that space
 			 * should be our eventual 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;
+			assert(graph->mapping[i - 1] > target);
+			assert(graph->mapping[i - 2] < 0);
+			assert(graph->mapping[i - 3] == target);
+			graph->mapping[i - 2] = target;
 			/*
 			 * Mark this branch as the horizontal edge to
 			 * prevent any other edges from moving
@@ -1209,14 +1214,14 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 	/*
 	 * The new mapping may be 1 smaller than the old mapping
 	 */
-	if (graph->new_mapping[graph->mapping_size - 1] < 0)
+	if (graph->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->new_mapping[i];
+		int target = graph->mapping[i];
 		if (target < 0)
 			graph_line_addch(line, ' ');
 		else if (target * 2 == i)
@@ -1229,22 +1234,17 @@ 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->new_mapping[i] = -1;
+					graph->mapping[i] = -1;
 				used_horizontal = 1;
 			graph_line_write_column(line, &graph->new_columns[target], '_');
 		} else {
 			if (used_horizontal && i < horizontal_edge)
-				graph->new_mapping[i] = -1;
+				graph->mapping[i] = -1;
 			graph_line_write_column(line, &graph->new_columns[target], '/');
 
 		}
 	}
 
-	/*
-	 * 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.
-- 
cgit v1.2.3


From 479db18bc0c38ed610fba56f3cc98abd7977e695 Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:57 +0000
Subject: graph: smooth appearance of collapsing edges on commit lines

When a graph contains edges that are in the process of collapsing to the
left, but those edges cross a commit line, the effect is that the edges
have a jagged appearance:

        *
        |\
        | *
        |  \
        *-. \
        |\ \ \
        | | * |
        | * | |
        | |/ /
        * | |
        |/ /
        * |
        |/
        *

We already takes steps to smooth edges like this when they're expanding;
when an edge appears to the right of a merge commit marker on a
GRAPH_COMMIT line immediately following a GRAPH_POST_MERGE line, we
render it as a `\`:

        * \
        |\ \
        | * \
        | |\ \

We can make a similar improvement to collapsing edges, making them
easier to follow and giving the overall graph a feeling of increased
symmetry:

        *
        |\
        | *
        |  \
        *-. \
        |\ \ \
        | | * |
        | * | |
        | |/ /
        * / /
        |/ /
        * /
        |/
        *

To do this, we introduce a new special case for edges on GRAPH_COMMIT
lines that immediately follow a GRAPH_COLLAPSING line. By retaining a
copy of the `mapping` array used to render the GRAPH_COLLAPSING line in
the `old_mapping` array, we can determine that an edge is collapsing
through the GRAPH_COMMIT line and should be smoothed.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 17 +++++++++++++----
 1 file changed, 13 insertions(+), 4 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index 2315f3604d..63f8d18baa 100644
--- a/graph.c
+++ b/graph.c
@@ -297,10 +297,10 @@ struct git_graph {
 	 */
 	int *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.
+	 * 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.
 	 */
 	int *old_mapping;
 	/*
@@ -1015,6 +1015,10 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 				graph_line_write_column(line, 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, '/');
 		} else {
 			graph_line_write_column(line, col, '|');
 		}
@@ -1211,6 +1215,11 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 		}
 	}
 
+	/*
+	 * 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
 	 */
-- 
cgit v1.2.3


From 92beecc136ad51f358baacf948b4c4b734fd5a4c Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:58 +0000
Subject: graph: flatten edges that fuse with their right neighbor

When a merge commit is printed and its final parent is the same commit
that occupies the column to the right of the merge, this results in a
kink in the displayed edges:

        * |
        |\ \
        | |/
        | *

Graphs containing these shapes can be hard to read, as the expansion to
the right followed immediately by collapsing back to the left creates a
lot of zig-zagging edges, especially when many columns are present.

We can improve this by eliminating the zig-zag and having the merge's
final parent edge fuse immediately with its neighbor:

        * |
        |\|
        | *

This reduces the horizontal width for the current commit by 2, and
requires one less row, making the graph display more compact. Taken in
combination with other graph-smoothing enhancements, it greatly
compresses the space needed to display certain histories:

        *
        |\
        | *                       *
        | |\                      |\
        | | *                     | *
        | | |                     | |\
        | |  \                    | | *
        | *-. \                   | * |
        | |\ \ \        =>        |/|\|
        |/ / / /                  | | *
        | | | /                   | * |
        | | |/                    | |/
        | | *                     * /
        | * |                     |/
        | |/                      *
        * |
        |/
        *

One of the test cases here cannot be correctly rendered in Git v2.23.0;
it produces this output following commit E:

        | | *-. \   5_E
        | | |\ \ \
        | |/ / / /
        | | | / _
        | |_|/
        |/| |

The new implementation makes sure that the rightmost edge in this
history is not left dangling as above.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 34 ++++++++++++++++++++++++++--------
 1 file changed, 26 insertions(+), 8 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index 63f8d18baa..80db74aee6 100644
--- a/graph.c
+++ b/graph.c
@@ -557,8 +557,24 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 		shift = (dist > 1) ? 2 * dist - 3 : 1;
 
 		graph->merge_layout = (dist > 0) ? 0 : 1;
+		graph->edges_added = graph->num_parents + graph->merge_layout  - 2;
+
 		mapping_idx = graph->width + (graph->merge_layout - 1) * shift;
 		graph->width += 2 * graph->merge_layout;
+
+	} 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;
@@ -604,6 +620,8 @@ static void graph_update_columns(struct git_graph *graph)
 		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
@@ -731,9 +749,6 @@ void graph_update(struct git_graph *graph, struct commit *commit)
 	 */
 	graph_update_columns(graph);
 
-	graph->prev_edges_added = graph->edges_added;
-	graph->edges_added = graph->num_parents + graph->merge_layout - 2;
-
 	graph->expansion_row = 0;
 
 	/*
@@ -1041,7 +1056,7 @@ const char merge_chars[] = {'/', '|', '\\'};
 static void graph_output_post_merge_line(struct git_graph *graph, struct graph_line *line)
 {
 	int seen_this = 0;
-	int i;
+	int i, j;
 
 	struct commit_list *first_parent = first_interesting_parent(graph);
 	int seen_parent = 0;
@@ -1073,16 +1088,19 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 			char c;
 			seen_this = 1;
 
-			for (; parents; parents = next_interesting_parent(graph, parents)) {
+			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)
-					graph_line_addch(line, ' ');
-				else
+				if (idx == 2) {
+					if (graph->edges_added > 0 || j < graph->num_parents - 1)
+						graph_line_addch(line, ' ');
+				} else {
 					idx++;
+				}
+				parents = next_interesting_parent(graph, parents);
 			}
 			if (graph->edges_added == 0)
 				graph_line_addch(line, ' ');
-- 
cgit v1.2.3


From bbb13e8188ee37dd3e2318752342622266659620 Mon Sep 17 00:00:00 2001
From: James Coglan <jcoglan@gmail.com>
Date: Tue, 15 Oct 2019 23:47:59 +0000
Subject: graph: fix coloring of octopus dashes

In 04005834ed ("log: fix coloring of certain octopus merge shapes",
2018-09-01) there is a fix for the coloring of dashes following an
octopus merge. It makes a distinction between the case where all parents
introduce a new column, versus the case where the first parent collapses
into an existing column:

        | *-.           | *-.
        | |\ \          | |\ \
        | | | |         |/ / /

The latter case means that the columns for the merge parents begin one
place to the left in the `new_columns` array compared to the former
case.

However, the implementation only works if the commit's parents are kept
in order as they map onto the visual columns, as we get the colors by
iterating over `new_columns` as we print the dashes. In general, the
commit's parents can arbitrarily merge with existing columns, and change
their ordering in the process.

For example, in the following diagram, the number of each column
indicates which commit parent appears in each column.

        | | *---.
        | | |\ \ \
        | | |/ / /
        | |/| | /
        | |_|_|/
        |/| | |
        3 1 0 2

If the columns are colored (red, green, yellow, blue), then the dashes
will currently be colored yellow and blue, whereas they should be blue
and red.

To fix this, we need to look up each column in the `mapping` array,
which before the `GRAPH_COLLAPSING` state indicates which logical column
is displayed in each visual column. This implementation is simpler as it
doesn't have any edge cases, and it also handles how left-skewed first
parents are now displayed:

        | *-.
        |/|\ \
        | | | |
        0 1 2 3

The color of the first dashes is always the color found in `mapping` two
columns to the right of the commit symbol. Because commits are displayed
after all edges have been collapsed together and the visual columns
match the logical ones, we can find the visual offset of the commit
symbol using `commit_index`.

Signed-off-by: James Coglan <jcoglan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 71 ++++++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 37 insertions(+), 34 deletions(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index 80db74aee6..e3fd0ea5f8 100644
--- a/graph.c
+++ b/graph.c
@@ -684,6 +684,11 @@ static void graph_update_columns(struct git_graph *graph)
 		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)
 {
 	/*
@@ -706,7 +711,7 @@ static int graph_num_expansion_rows(struct git_graph *graph)
 	 * 		| * \
 	 * 		|/|\ \
 	 */
-	return (graph->num_parents + graph->merge_layout - 3) * 2;
+	return graph_num_dashed_parents(graph) * 2;
 }
 
 static int graph_needs_pre_commit_line(struct git_graph *graph)
@@ -934,47 +939,45 @@ static void graph_output_commit_char(struct git_graph *graph, struct graph_line
 static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line *line)
 {
 	/*
-	 * 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.
+	 * The parents of a merge commit can be arbitrarily reordered as they
+	 * are mapped onto display columns, for example this is a valid merge:
 	 *
-	 * | *---.
-	 * | |\ \ \
-	 * | | | | |
-	 * x 0 1 2 3
+	 *	| | *---.
+	 *	| | |\ \ \
+	 *	| | |/ / /
+	 *	| |/| | /
+	 *	| |_|_|/
+	 *	|/| | |
+	 *	3 1 0 2
 	 *
-	 */
-	const int dashless_parents = 3 - graph->merge_layout;
-	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:
+	 * 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.
 	 *
-	 * | *-.
-	 * |/|\ \
-	 * | | | |
-	 * x 0 1 2
+	 * 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.
 	 *
-	 * In which case the number of parents will be one greater than the
-	 * number of added columns.
+	 * 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.
 	 */
-	int added_cols = (graph->num_new_columns - graph->num_columns);
-	int parent_in_old_cols = graph->num_parents - added_cols;
 
-	/*
-	 * In both cases, commit_index corresponds to the edge labeled "0".
-	 */
-	int first_col = graph->commit_index + dashless_parents
-	    - parent_in_old_cols;
+	int i, j;
+	struct column *col;
 
-	int i;
-	for (i = 0; i < dashful_parents; i++) {
-		graph_line_write_column(line, &graph->new_columns[i+first_col], '-');
-		graph_line_write_column(line, &graph->new_columns[i+first_col],
-					  i == dashful_parents-1 ? '.' : '-');
+	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];
+
+		graph_line_write_column(line, col, '-');
+		graph_line_write_column(line, col, (i == dashed_parents - 1) ? '.' : '-');
 	}
+
+	return;
 }
 
 static void graph_output_commit_line(struct git_graph *graph, struct graph_line *line)
-- 
cgit v1.2.3


From 3f1480b745b70e9f7c0629b58a98ddcb516490bb Mon Sep 17 00:00:00 2001
From: Heba Waly <heba.waly@gmail.com>
Date: Sun, 17 Nov 2019 21:04:42 +0000
Subject: graph: move doc to graph.h and graph.c

Move the documentation from Documentation/technical/api-history-graph.txt to
graph.h and graph.c as it's easier for the developers to find the usage
information beside the code instead of looking for it in another doc file.

The graph library was already well documented, so few comments were added to
both graph.h and graph.c

Also documentation/technical/api-history-graph.txt is removed because
the information it has is now redundant and it'll be hard to keep it up to
date and synchronized with the documentation in the header file.

Signed-off-by: Heba Waly <heba.waly@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 1 +
 1 file changed, 1 insertion(+)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index f53135485f..eab3af1dc7 100644
--- a/graph.c
+++ b/graph.c
@@ -34,6 +34,7 @@ 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,
-- 
cgit v1.2.3


From 571fb9657318b710825cde19b70f7da4392abd44 Mon Sep 17 00:00:00 2001
From: ryenus <ryenus@gmail.com>
Date: Sun, 15 Dec 2019 15:12:24 +0000
Subject: fix-typo: consecutive-word duplications

Correct unintentional duplication(s) of words, such as "the the",
and "can can" etc.

The changes are only applied to cases where it's fixing what is clearly
wrong or prone to misunderstanding, as suggested by the reviewers.

Helped-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Helped-by: Denton Liu <liu.denton@gmail.com>
Helped-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: ryenus <ryenus@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 graph.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'graph.c')

diff --git a/graph.c b/graph.c
index e3fd0ea5f8..5da111f567 100644
--- a/graph.c
+++ b/graph.c
@@ -218,7 +218,7 @@ struct git_graph {
 	int merge_layout;
 	/*
 	 * The number of columns added to the graph by the current commit. For
-	 * 2-way and octopus merges, this is is usually one less than the
+	 * 2-way and octopus merges, this is usually one less than the
 	 * number of parents:
 	 *
 	 * 		| | |			| |    \
-- 
cgit v1.2.3