git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v3 12/13] graph: flatten edges that fuse with their right neighbor

From
James Coglan via GitGitGadget <gitgitgadget@gmail.com>
Date
Oct 15, 2019, 23:47 UTC
Message-ID
<04ba5169bc855ae4a65c33a0484926c22e68714a.1571183279.git.gitgitgadget@gmail.com>
In-Reply-To
<pull.383.v3.git.1571183279.gitgitgadget@gmail.com>
From: James Coglan <jcoglan@gmail.com>

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>
---
 graph.c                                    | 34 +++++++++----
 t/t4215-log-skewed-merges.sh               | 56 ++++++++++++++++++----
 t/t6016-rev-list-graph-simplify-history.sh | 30 +++++-------
 3 files changed, 86 insertions(+), 34 deletions(-)
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, ' ');
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 1745b3b64c..d33c6438d8 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -11,9 +11,8 @@ test_expect_success 'log --graph with merge fusing with its left and right neigh
 	| *   G
 	| |\
 	| | * F
-	| * |   E
-	|/|\ \
-	| | |/
+	| * | E
+	|/|\|
 	| | * D
 	| * | C
 	| |/
@@ -43,9 +42,9 @@ test_expect_success 'log --graph with left-skewed merge' '
 	| | | | * 0_G
 	| |_|_|/|
 	|/| | | |
-	| | | * |   0_F
-	| |_|/|\ \
-	|/| | | |/
+	| | | * | 0_F
+	| |_|/|\|
+	|/| | | |
 	| | | | * 0_E
 	| |_|_|/
 	|/| | |
@@ -153,9 +152,8 @@ test_expect_success 'log --graph with nested right-skewed merge following left-s
 	| | * 3_G
 	| * | 3_F
 	|/| |
-	| * |   3_E
-	| |\ \
-	| | |/
+	| * | 3_E
+	| |\|
 	| | * 3_D
 	| * | 3_C
 	| |/
@@ -216,4 +214,44 @@ test_expect_success 'log --graph with right-skewed merge following a left-skewed
 	test_cmp expect actual
 '
 
+test_expect_success 'log --graph with octopus merge with column joining its penultimate parent' '
+	cat >expect <<-\EOF &&
+	*   5_H
+	|\
+	| *-.   5_G
+	| |\ \
+	| | | * 5_F
+	| | * |   5_E
+	| |/|\ \
+	| |_|/ /
+	|/| | /
+	| | |/
+	* | | 5_D
+	| | * 5_C
+	| |/
+	|/|
+	| * 5_B
+	|/
+	* 5_A
+	EOF
+
+	git checkout --orphan 5_p &&
+	test_commit 5_A &&
+	git branch 5_q &&
+	git branch 5_r &&
+	test_commit 5_B &&
+	git checkout 5_q && test_commit 5_C &&
+	git checkout 5_r && test_commit 5_D &&
+	git checkout 5_p &&
+	git merge --no-ff 5_q 5_r -m 5_E &&
+	git checkout 5_q && test_commit 5_F &&
+	git checkout -b 5_s 5_p^ &&
+	git merge --no-ff 5_p 5_q -m 5_G &&
+	git checkout 5_r &&
+	git merge --no-ff 5_s -m 5_H &&
+
+	git log --graph --pretty=tformat:%s | sed "s/ *$//" >actual &&
+	test_cmp expect actual
+'
+
 test_done
diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh
index ca1682f29b..f5e6e92f5b 100755
--- a/t/t6016-rev-list-graph-simplify-history.sh
+++ b/t/t6016-rev-list-graph-simplify-history.sh
@@ -67,11 +67,10 @@ test_expect_success '--graph --all' '
 	echo "| * $C4" >> expected &&
 	echo "| * $C3" >> expected &&
 	echo "* | $A5" >> expected &&
-	echo "| |     " >> expected &&
-	echo "|  \\    " >> expected &&
-	echo "*-. \\   $A4" >> expected &&
-	echo "|\\ \\ \\  " >> expected &&
-	echo "| | |/  " >> expected &&
+	echo "| |   " >> expected &&
+	echo "|  \\  " >> expected &&
+	echo "*-. | $A4" >> expected &&
+	echo "|\\ \\| " >> expected &&
 	echo "| | * $C2" >> expected &&
 	echo "| | * $C1" >> expected &&
 	echo "| * | $B2" >> expected &&
@@ -97,11 +96,10 @@ test_expect_success '--graph --simplify-by-decoration' '
 	echo "| * $C4" >> expected &&
 	echo "| * $C3" >> expected &&
 	echo "* | $A5" >> expected &&
-	echo "| |     " >> expected &&
-	echo "|  \\    " >> expected &&
-	echo "*-. \\   $A4" >> expected &&
-	echo "|\\ \\ \\  " >> expected &&
-	echo "| | |/  " >> expected &&
+	echo "| |   " >> expected &&
+	echo "|  \\  " >> expected &&
+	echo "*-. | $A4" >> expected &&
+	echo "|\\ \\| " >> expected &&
 	echo "| | * $C2" >> expected &&
 	echo "| | * $C1" >> expected &&
 	echo "| * | $B2" >> expected &&
@@ -131,9 +129,8 @@ test_expect_success '--graph --simplify-by-decoration prune branch B' '
 	echo "| * $C4" >> expected &&
 	echo "| * $C3" >> expected &&
 	echo "* | $A5" >> expected &&
-	echo "* |   $A4" >> expected &&
-	echo "|\\ \\  " >> expected &&
-	echo "| |/  " >> expected &&
+	echo "* | $A4" >> expected &&
+	echo "|\\| " >> expected &&
 	echo "| * $C2" >> expected &&
 	echo "| * $C1" >> expected &&
 	echo "* | $A3" >> expected &&
@@ -151,10 +148,9 @@ test_expect_success '--graph --full-history -- bar.txt' '
 	echo "|\\  " >> expected &&
 	echo "| * $C4" >> expected &&
 	echo "* | $A5" >> expected &&
-	echo "* |   $A4" >> expected &&
-	echo "|\\ \\  " >> expected &&
-	echo "| |/  " >> expected &&
-	echo "* / $A3" >> expected &&
+	echo "* | $A4" >> expected &&
+	echo "|\\| " >> expected &&
+	echo "* | $A3" >> expected &&
 	echo "|/  " >> expected &&
 	echo "* $A2" >> expected &&
 	git rev-list --graph --full-history --all -- bar.txt > actual &&

-- 
gitgitgadget
Previous: James Coglan via GitGitGadgetNext: James Coglan via GitGitGadget
Message 82 of 83 in “Improve the readability of log --graph output”
  1. 00/11 Improve the readability of log --graph outputJames Coglan via GitGitGadget, Oct 10, 2019
  2. 01/11 graph: automatically track visible width of `strbuf`James Coglan via GitGitGadget, Oct 10, 2019
  3. Johannes SchindelinOct 10, 2019
  4. Denton LiuOct 10, 2019
  5. Derrick StoleeOct 11, 2019
  6. Junio C HamanoOct 11, 2019
  7. Denton LiuOct 11, 2019
  8. Johannes SchindelinOct 11, 2019
  9. James CoglanOct 11, 2019
  10. Junio C HamanoOct 12, 2019
  11. Johannes SchindelinOct 12, 2019
  12. James CoglanOct 14, 2019
  13. James CoglanOct 14, 2019
  14. Junio C HamanoOct 16, 2019
  15. Junio C HamanoOct 11, 2019
  16. James CoglanOct 11, 2019
  17. 03/11 graph: reduce duplication in `graph_insert_into_new_columns()`James Coglan via GitGitGadget, Oct 10, 2019
  18. 02/11 graph: reuse `find_new_column_by_commit()`James Coglan via GitGitGadget, Oct 10, 2019
  19. 04/11 graph: remove `mapping_idx` and `graph_update_width()`James Coglan via GitGitGadget, Oct 10, 2019
  20. 05/11 graph: extract logic for moving to GRAPH_PRE_COMMIT stateJames Coglan via GitGitGadget, Oct 10, 2019
  21. 09/11 graph: smooth appearance of collapsing edges on commit linesJames Coglan via GitGitGadget, Oct 10, 2019
  22. 08/11 graph: rename `new_mapping` to `old_mapping`James Coglan via GitGitGadget, Oct 10, 2019
  23. 11/11 graph: fix coloring of octopus dashesJames Coglan via GitGitGadget, Oct 10, 2019
  24. Denton LiuOct 10, 2019
  25. Denton LiuOct 10, 2019
  26. Jeff KingOct 13, 2019
  27. 07/11 graph: commit and post-merge lines for left-skewed mergesJames Coglan via GitGitGadget, Oct 10, 2019
  28. Derrick StoleeOct 10, 2019
  29. James CoglanOct 11, 2019
  30. Jeff KingOct 13, 2019
  31. James CoglanOct 14, 2019
  32. Derrick StoleeOct 14, 2019
  33. Johannes SchindelinOct 14, 2019
  34. 06/11 graph: tidy up display of left-skewed mergesJames Coglan via GitGitGadget, Oct 10, 2019
  35. Derrick StoleeOct 10, 2019
  36. James CoglanOct 11, 2019
  37. Derrick StoleeOct 12, 2019
  38. James CoglanOct 14, 2019
  39. 10/11 graph: flatten edges that join to their right neighborJames Coglan via GitGitGadget, Oct 10, 2019
  40. Derrick StoleeOct 10, 2019
  41. Jeff KingOct 13, 2019
  42. James CoglanOct 14, 2019
  43. 00/13 Improve the readability of log --graph outputJames Coglan via GitGitGadget, Oct 15, 2019
  44. 03/13 graph: reuse `find_new_column_by_commit()`James Coglan via GitGitGadget, Oct 15, 2019
  45. 02/13 graph: handle line padding in `graph_next_line()`James Coglan via GitGitGadget, Oct 15, 2019
  46. 05/13 graph: remove `mapping_idx` and `graph_update_width()`James Coglan via GitGitGadget, Oct 15, 2019
  47. 01/13 graph: automatically track display width of graph linesJames Coglan via GitGitGadget, Oct 15, 2019
  48. 04/13 graph: reduce duplication in `graph_insert_into_new_columns()`James Coglan via GitGitGadget, Oct 15, 2019
  49. 06/13 graph: extract logic for moving to GRAPH_PRE_COMMIT stateJames Coglan via GitGitGadget, Oct 15, 2019
  50. 09/13 graph: commit and post-merge lines for left-skewed mergesJames Coglan via GitGitGadget, Oct 15, 2019
  51. 07/13 graph: example of graph output that can be simplifiedJames Coglan via GitGitGadget, Oct 15, 2019
  52. 11/13 graph: smooth appearance of collapsing edges on commit linesJames Coglan via GitGitGadget, Oct 15, 2019
  53. 08/13 graph: tidy up display of left-skewed mergesJames Coglan via GitGitGadget, Oct 15, 2019
  54. 12/13 graph: flatten edges that fuse with their right neighborJames Coglan via GitGitGadget, Oct 15, 2019
  55. 10/13 graph: rename `new_mapping` to `old_mapping`James Coglan via GitGitGadget, Oct 15, 2019
  56. 13/13 graph: fix coloring of octopus dashesJames Coglan via GitGitGadget, Oct 15, 2019
  57. 00/13 Improve the readability of log --graph outputJames Coglan via GitGitGadget, Oct 15, 2019
  58. 03/13 graph: reuse `find_new_column_by_commit()`James Coglan via GitGitGadget, Oct 15, 2019
  59. 02/13 graph: handle line padding in `graph_next_line()`James Coglan via GitGitGadget, Oct 15, 2019
  60. Junio C HamanoOct 16, 2019
  61. 01/13 graph: automatically track display width of graph linesJames Coglan via GitGitGadget, Oct 15, 2019
  62. Junio C HamanoOct 16, 2019
  63. Junio C HamanoOct 16, 2019
  64. 04/13 graph: reduce duplication in `graph_insert_into_new_columns()`James Coglan via GitGitGadget, Oct 15, 2019
  65. 06/13 graph: extract logic for moving to GRAPH_PRE_COMMIT stateJames Coglan via GitGitGadget, Oct 15, 2019
  66. 05/13 graph: remove `mapping_idx` and `graph_update_width()`James Coglan via GitGitGadget, Oct 15, 2019
  67. 07/13 graph: example of graph output that can be simplifiedJames Coglan via GitGitGadget, Oct 15, 2019
  68. Derrick StoleeOct 17, 2019
  69. SZEDER GáborOct 18, 2019
  70. t4215: don't put git commands upstream of pipeDenton Liu, Nov 12, 2019
  71. Junio C HamanoNov 12, 2019
  72. SZEDER GáborNov 12, 2019
  73. t4215: use helper function to check outputDenton Liu, Nov 12, 2019
  74. Junio C HamanoNov 13, 2019
  75. 09/13 graph: commit and post-merge lines for left-skewed mergesJames Coglan via GitGitGadget, Oct 15, 2019
  76. 13/13 graph: fix coloring of octopus dashesJames Coglan via GitGitGadget, Oct 15, 2019
  77. 08/13 graph: tidy up display of left-skewed mergesJames Coglan via GitGitGadget, Oct 15, 2019
  78. Junio C HamanoOct 16, 2019
  79. Derrick StoleeOct 17, 2019
  80. Junio C HamanoOct 18, 2019
  81. 10/13 graph: rename `new_mapping` to `old_mapping`James Coglan via GitGitGadget, Oct 15, 2019
  82. 12/13 graph: flatten edges that fuse with their right neighborJames Coglan via GitGitGadget, Oct 15, 2019
  83. 11/13 graph: smooth appearance of collapsing edges on commit linesJames Coglan via GitGitGadget, Oct 15, 2019

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.