[GSoC PATCH v3 1/1] graph: add indentation for commits preceded by a parentless commit

[Pablo Sabater <pabloosabaterr@gmail.com>]

When having a history with multiple root commits or commits
that act like roots (they have excluded parents), let's call
them parentless, and drawing the history near them, the
graphing engine renders the commits one below the other, seeming
that they are related.

This issue has been attempted multiple times:
  https://lore.kernel.org/git/xmqqwnwajbuj.fsf@gitster.c.googlers.com/

This happens because for these parentless commits, in the next
row the column becomes empty and the engine prints from left
to right from the first empty column, filling the gap below
these parentless commits.

Keep a parentless commit for at least one row more to avoid
having the column empty but hide it as indentation,
therefore making the next unrelated commit live in
the next column (column means even positions where edges live:
0, 2, 4), then clean that "placeholder" column and let
the unrelated commit to naturally collapse to the column
where the parentless commit was.

Add is_placeholder to the struct column to mark if a column
is acting as a placeholder for the padding.

When a column is parentless, add a column with the parentless
commit data to prevent segfaults when 'column->commit' and
mark it as a placeholder.

Teach rendering functions to print a padding ' ' instead of
an edge when a placeholder column is met.

Then, unless the next commit is also parentless (then we
need to keep cascading the indentation) clean the mapping
and columns from the placeholder to allow it to
collapse naturally.

Add tests for different cases.

before this patch:

* parentless A
* child B
* parentless B

after this patch:

* parentless A
  * child B
 /
* parentless B

Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
---
 graph.c                      | 115 ++++++++++++++++++++++++++++++--
 t/t4215-log-skewed-merges.sh | 124 +++++++++++++++++++++++++++++++++++
 2 files changed, 233 insertions(+), 6 deletions(-)

diff --git a/graph.c b/graph.c
index 26f6fbf000..97292df998 100644
--- a/graph.c
+++ b/graph.c
@@ -60,6 +60,12 @@ struct column {
 	 * index into column_colors.
 	 */
 	unsigned short color;
+	/*
+	 * A placeholder column keeps the column of a parentless commit filled
+	 * for one extra row, avoiding a next unrelated commit to be printed
+	 * in the same column.
+	 */
+	unsigned is_placeholder:1;
 };

 enum graph_state {
@@ -563,6 +569,7 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 		i = graph->num_new_columns++;
 		graph->new_columns[i].commit = commit;
 		graph->new_columns[i].color = graph_find_commit_color(graph, commit);
+		graph->new_columns[i].is_placeholder = 0;
 	}

 	if (graph->num_parents > 1 && idx > -1 && graph->merge_layout == -1) {
@@ -607,7 +614,7 @@ static void graph_update_columns(struct git_graph *graph)
 {
 	struct commit_list *parent;
 	int max_new_columns;
-	int i, seen_this, is_commit_in_columns;
+	int i, seen_this, is_commit_in_columns, is_parentless;

 	/*
 	 * Swap graph->columns with graph->new_columns
@@ -654,6 +661,26 @@ static void graph_update_columns(struct git_graph *graph)
 	 */
 	seen_this = 0;
 	is_commit_in_columns = 1;
+	/*
+	 * A commit is "parentless" (is a visual root that starts a new column)
+	 * only if has no visible parents AND it's not a boundary commit.
+	 *
+	 * Boundary commits also have no visible parents, but they are
+	 * NOT a visual root:
+	 *
+	 * 1. A boundary only appears in the output because an included commit
+	 *    is its child. Children are always above, and the renderer draws an
+	 *    edge down to the boundary from that child. Rather than starting
+	 *    a column like a visual root would do, it "inherits" its child
+	 *    column.
+	 *
+	 * 2. Included commit CAN'T appear below a boundary. Boundaries are
+	 *    ancestors of the exclusion point; if an included commit were an
+	 *    ancestor of the boundary it would be excluded and not rendered.
+	 *    Boundaries therefore always sink to the bottom.
+	 */
+	is_parentless = graph->num_parents == 0 &&
+			!(graph->commit->object.flags & BOUNDARY);
 	for (i = 0; i <= graph->num_columns; i++) {
 		struct commit *col_commit;
 		if (i == graph->num_columns) {
@@ -688,11 +715,46 @@ static void graph_update_columns(struct git_graph *graph)
 			 * least 2, even if it has no interesting parents.
 			 * The current commit always takes up at least 2
 			 * spaces.
+			 *
+			 * Check for the commit to seem like a root, no parents
+			 * rendered and that it is not a boundary commit. If so,
+			 * add a placeholder to keep that column filled for
+			 * at least one row.
+			 *
+			 * Prevents the next commit from being inserted
+			 * just below and making the graph confusing.
 			 */
-			if (graph->num_parents == 0)
+			if (is_parentless) {
+				graph_insert_into_new_columns(graph, graph->commit, i);
+				graph->new_columns[graph->num_new_columns - 1]
+							    .is_placeholder = 1;
+			} else if (graph->num_parents == 0) {
 				graph->width += 2;
+			}
 		} else {
-			graph_insert_into_new_columns(graph, col_commit, -1);
+			if (graph->columns[i].is_placeholder) {
+				/*
+				 * Keep the placeholders if the next commit is
+				 * parentless also, making the indentation cascade.
+				 */
+				if (!seen_this && is_parentless) {
+					graph_insert_into_new_columns(graph,
+							graph->columns[i].commit, i);
+					graph->new_columns[graph->num_new_columns - 1]
+							.is_placeholder = 1;
+				} else if (!seen_this) {
+					graph->mapping[graph->width] = -1;
+					graph->width += 2;
+				}
+				/*
+				 * seen_this && is_placeholder means that this
+				 * line is the one after the indented one, the
+				 * placeholder is no longer needed, gets
+				 * dropped and the columns collapses naturally.
+				 */
+			} else {
+				graph_insert_into_new_columns(graph, col_commit, -1);
+			}
 		}
 	}

@@ -846,7 +908,10 @@ 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++) {
-		graph_line_write_column(line, &graph->new_columns[i], '|');
+		if (graph->new_columns[i].is_placeholder)
+			graph_line_write_column(line, &graph->new_columns[i], ' ');
+		else
+			graph_line_write_column(line, &graph->new_columns[i], '|');
 		graph_line_addch(line, ' ');
 	}
 }
@@ -1058,7 +1123,34 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 			   graph->mapping[2 * i] < i) {
 			graph_line_write_column(line, col, '/');
 		} else {
-			graph_line_write_column(line, col, '|');
+			if (col->is_placeholder) {
+				/*
+				 * When the indented commit is a merge commit,
+				 * the placeholder column adds unwanted padding
+				 * between the commit and its subject.
+				 *
+				 *   * parentless commit
+				 *     * merge commit
+				 *    /|
+				 *   | * parent A
+				 *   *   parent B
+				 *     ^^ unwanted padding
+				 *
+				 * Once the current commit has been seen, don't
+				 * let placeholder columns to be rendered:
+				 *
+				 *   * parentless commit
+				 *     * merge commit
+				 *    /|
+				 *   | * parent A
+				 *   * parent B
+				 */
+				if (seen_this)
+					continue;
+				graph_line_write_column(line, col, ' ');
+			} else {
+				graph_line_write_column(line, col, '|');
+			}
 		}
 		graph_line_addch(line, ' ');
 	}
@@ -1135,7 +1227,18 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 				graph_line_write_column(line, col, '|');
 			graph_line_addch(line, ' ');
 		} else {
-			graph_line_write_column(line, col, '|');
+			if (col->is_placeholder) {
+				/*
+				 * Same placeholder handling as in
+				 * graph_output_commit_line().
+				 */
+				if (seen_this)
+					continue;
+				graph_line_write_column(line, col, ' ');
+			} else {
+				graph_line_write_column(line, col, '|');
+			}
+
 			if (graph->merge_layout != 0 || i != graph->commit_index - 1) {
 				if (parent_col)
 					graph_line_write_column(
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 28d0779a8c..0f6f95a6b5 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -370,4 +370,128 @@ test_expect_success 'log --graph with multiple tips' '
 	EOF
 '

+test_expect_success 'log --graph with root commit' '
+	git checkout --orphan 8_1 && test_commit 8_A && test_commit 8_A1 &&
+	git checkout --orphan 8_2 && test_commit 8_B &&
+
+	check_graph 8_2 8_1 <<-\EOF
+	* 8_B
+	  * 8_A1
+	 /
+	* 8_A
+	EOF
+'
+
+test_expect_success 'log --graph with multiple root commits' '
+	test_commit 8_B1 &&
+	git checkout --orphan 8_3 && test_commit 8_C &&
+
+	check_graph 8_3 8_2 8_1 <<-\EOF
+	* 8_C
+	  * 8_B1
+	 /
+	* 8_B
+	  * 8_A1
+	 /
+	* 8_A
+	EOF
+'
+
+test_expect_success 'log --graph commit from a two parent merge shifted' '
+	git checkout --orphan 9_1 && test_commit 9_B &&
+	git checkout --orphan 9_2 && test_commit 9_C &&
+	git checkout 9_1 &&
+	git merge 9_2 --allow-unrelated-histories -m 9_M &&
+	git checkout --orphan 9_3 &&
+	test_commit 9_A && test_commit 9_A1 && test_commit 9_A2 &&
+
+	check_graph 9_3 9_1 <<-\EOF
+	* 9_A2
+	* 9_A1
+	* 9_A
+	  * 9_M
+	 /|
+	| * 9_C
+	* 9_B
+	EOF
+'
+
+test_expect_success 'log --graph commit from a three parent merge shifted' '
+	git checkout --orphan 10_1 && test_commit 10_B &&
+	git checkout --orphan 10_2 && test_commit 10_C &&
+	git checkout --orphan 10_3 && test_commit 10_D &&
+	git checkout 10_1 &&
+	TREE=$(git write-tree) &&
+	MERGE=$(git commit-tree $TREE -p 10_1 -p 10_2 -p 10_3 -m 10_M) &&
+	git reset --hard $MERGE &&
+	git checkout --orphan 10_4 &&
+	test_commit 10_A && test_commit 10_A1 && test_commit 10_A2 &&
+
+	check_graph 10_4 10_1 <<-\EOF
+	* 10_A2
+	* 10_A1
+	* 10_A
+	  *   10_M
+	 /|\
+	| | * 10_D
+	| * 10_C
+	* 10_B
+	EOF
+'
+
+test_expect_success 'log --graph commit from a four parent merge shifted' '
+	git checkout --orphan 11_1 && test_commit 11_B &&
+	git checkout --orphan 11_2 && test_commit 11_C &&
+	git checkout --orphan 11_3 && test_commit 11_D &&
+	git checkout --orphan 11_4 && test_commit 11_E &&
+	git checkout 11_1 &&
+	TREE=$(git write-tree) &&
+	MERGE=$(git commit-tree $TREE -p 11_1 -p 11_2 -p 11_3 -p 11_4 -m 11_M) &&
+	git reset --hard $MERGE &&
+	git checkout --orphan 11_5 &&
+	test_commit 11_A && test_commit 11_A1 && test_commit 11_A2 &&
+
+	check_graph 11_5 11_1 <<-\EOF
+	* 11_A2
+	* 11_A1
+	* 11_A
+	  *-.   11_M
+	 /|\ \
+	| | | * 11_E
+	| | * 11_D
+	| * 11_C
+	* 11_B
+	EOF
+'
+
+test_expect_success 'log --graph disconnected three roots cascading' '
+	git checkout --orphan 12_1 && test_commit 12_D && test_commit 12_D1 &&
+	git checkout --orphan 12_2 && test_commit 12_C &&
+	git checkout --orphan 12_3 && test_commit 12_B &&
+	git checkout --orphan 12_4 && test_commit 12_A &&
+
+	check_graph 12_4 12_3 12_2 12_1 <<-\EOF
+	* 12_A
+	  * 12_B
+	    * 12_C
+	      * 12_D1
+	   _ /
+	  /
+	 /
+	* 12_D
+	EOF
+'
+
+test_expect_success 'log --graph with excluded parent (not a root)' '
+	git checkout --orphan 13_1 && test_commit 13_X && test_commit 13_Y &&
+	git checkout --orphan 13_2 && test_commit 13_O && test_commit 13_A &&
+
+	check_graph 13_O..13_A 13_1 <<-\EOF
+	* 13_A
+	  * 13_Y
+	 /
+	* 13_X
+	EOF
+'
+
 test_done
--
2.43.0