Merge branch 'jc/log-graph-simplify'

The implementation of "git log --graph" got refactored and then its
output got simplified.

* jc/log-graph-simplify:
  t4215: use helper function to check output
  graph: fix coloring of octopus dashes
  graph: flatten edges that fuse with their right neighbor
  graph: smooth appearance of collapsing edges on commit lines
  graph: rename `new_mapping` to `old_mapping`
  graph: commit and post-merge lines for left-skewed merges
  graph: tidy up display of left-skewed merges
  graph: example of graph output that can be simplified
  graph: extract logic for moving to GRAPH_PRE_COMMIT state
  graph: remove `mapping_idx` and `graph_update_width()`
  graph: reduce duplication in `graph_insert_into_new_columns()`
  graph: reuse `find_new_column_by_commit()`
  graph: handle line padding in `graph_next_line()`
  graph: automatically track display width of graph lines

5 files changed, 287 insertions, 52 deletions

diff --git a/t/t3430-rebase-merges.sh b/t/t3430-rebase-merges.sh
index 9efcf4808a..a30d27e9f3 100755
--- a/t/t3430-rebase-merges.sh
+++ b/t/t3430-rebase-merges.sh
@@ -408,7 +408,7 @@ test_expect_success 'octopus merges' '
 	| | * three
 	| * | two
 	| |/
-	* | one
+	* / one
 	|/
 	o before-octopus
 	EOF
diff --git a/t/t4202-log.sh b/t/t4202-log.sh
index e803ba402e..ab0d021365 100755
--- a/t/t4202-log.sh
+++ b/t/t4202-log.sh
@@ -667,7 +667,7 @@ cat > expect <<\EOF
 * | | fifth
 * | | fourth
 |/ /
-* | third
+* / third
 |/
 * second
 * initial
diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh
index 3ae8e51e50..40d27db674 100755
--- a/t/t4214-log-graph-octopus.sh
+++ b/t/t4214-log-graph-octopus.sh
@@ -26,15 +26,14 @@ test_expect_success 'set up merge history' '
 test_expect_success 'log --graph with tricky octopus merge, no color' '
 	cat >expect.uncolored <<-\EOF &&
 	* left
-	| *---.   octopus-merge
-	| |\ \ \
-	|/ / / /
+	| *-.   octopus-merge
+	|/|\ \
 	| | | * 4
 	| | * | 3
 	| | |/
-	| * | 2
+	| * / 2
 	| |/
-	* | 1
+	* / 1
 	|/
 	* initial
 	EOF
@@ -47,15 +46,14 @@ test_expect_success 'log --graph with tricky octopus merge with colors' '
 	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
 	cat >expect.colors <<-\EOF &&
 	* left
-	<RED>|<RESET> *<BLUE>-<RESET><BLUE>-<RESET><MAGENTA>-<RESET><MAGENTA>.<RESET>   octopus-merge
-	<RED>|<RESET> <RED>|<RESET><YELLOW>\<RESET> <BLUE>\<RESET> <MAGENTA>\<RESET>
-	<RED>|<RESET><RED>/<RESET> <YELLOW>/<RESET> <BLUE>/<RESET> <MAGENTA>/<RESET>
+	<RED>|<RESET> *<MAGENTA>-<RESET><MAGENTA>.<RESET>   octopus-merge
+	<RED>|<RESET><RED>/<RESET><YELLOW>|<RESET><BLUE>\<RESET> <MAGENTA>\<RESET>
 	<RED>|<RESET> <YELLOW>|<RESET> <BLUE>|<RESET> * 4
 	<RED>|<RESET> <YELLOW>|<RESET> * <MAGENTA>|<RESET> 3
 	<RED>|<RESET> <YELLOW>|<RESET> <MAGENTA>|<RESET><MAGENTA>/<RESET>
-	<RED>|<RESET> * <MAGENTA>|<RESET> 2
+	<RED>|<RESET> * <MAGENTA>/<RESET> 2
 	<RED>|<RESET> <MAGENTA>|<RESET><MAGENTA>/<RESET>
-	* <MAGENTA>|<RESET> 1
+	* <MAGENTA>/<RESET> 1
 	<MAGENTA>|<RESET><MAGENTA>/<RESET>
 	* initial
 	EOF
@@ -74,9 +72,9 @@ test_expect_success 'log --graph with normal octopus merge, no color' '
 	| | | * 4
 	| | * | 3
 	| | |/
-	| * | 2
+	| * / 2
 	| |/
-	* | 1
+	* / 1
 	|/
 	* initial
 	EOF
@@ -92,9 +90,9 @@ test_expect_success 'log --graph with normal octopus merge with colors' '
 	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET> * 4
 	<RED>|<RESET> <GREEN>|<RESET> * <BLUE>|<RESET> 3
 	<RED>|<RESET> <GREEN>|<RESET> <BLUE>|<RESET><BLUE>/<RESET>
-	<RED>|<RESET> * <BLUE>|<RESET> 2
+	<RED>|<RESET> * <BLUE>/<RESET> 2
 	<RED>|<RESET> <BLUE>|<RESET><BLUE>/<RESET>
-	* <BLUE>|<RESET> 1
+	* <BLUE>/<RESET> 1
 	<BLUE>|<RESET><BLUE>/<RESET>
 	* initial
 	EOF
@@ -112,9 +110,9 @@ test_expect_success 'log --graph with normal octopus merge and child, no color'
 	| | | * 4
 	| | * | 3
 	| | |/
-	| * | 2
+	| * / 2
 	| |/
-	* | 1
+	* / 1
 	|/
 	* initial
 	EOF
@@ -123,7 +121,7 @@ test_expect_success 'log --graph with normal octopus merge and child, no color'
 	test_cmp expect.uncolored actual
 '
 
-test_expect_failure 'log --graph with normal octopus and child merge with colors' '
+test_expect_success 'log --graph with normal octopus and child merge with colors' '
 	cat >expect.colors <<-\EOF &&
 	* after-merge
 	*<BLUE>-<RESET><BLUE>-<RESET><MAGENTA>-<RESET><MAGENTA>.<RESET>   octopus-merge
@@ -131,9 +129,9 @@ test_expect_failure 'log --graph with normal octopus and child merge with colors
 	<GREEN>|<RESET> <YELLOW>|<RESET> <BLUE>|<RESET> * 4
 	<GREEN>|<RESET> <YELLOW>|<RESET> * <MAGENTA>|<RESET> 3
 	<GREEN>|<RESET> <YELLOW>|<RESET> <MAGENTA>|<RESET><MAGENTA>/<RESET>
-	<GREEN>|<RESET> * <MAGENTA>|<RESET> 2
+	<GREEN>|<RESET> * <MAGENTA>/<RESET> 2
 	<GREEN>|<RESET> <MAGENTA>|<RESET><MAGENTA>/<RESET>
-	* <MAGENTA>|<RESET> 1
+	* <MAGENTA>/<RESET> 1
 	<MAGENTA>|<RESET><MAGENTA>/<RESET>
 	* initial
 	EOF
@@ -147,15 +145,14 @@ test_expect_success 'log --graph with tricky octopus merge and its child, no col
 	cat >expect.uncolored <<-\EOF &&
 	* left
 	| * after-merge
-	| *---.   octopus-merge
-	| |\ \ \
-	|/ / / /
+	| *-.   octopus-merge
+	|/|\ \
 	| | | * 4
 	| | * | 3
 	| | |/
-	| * | 2
+	| * / 2
 	| |/
-	* | 1
+	* / 1
 	|/
 	* initial
 	EOF
@@ -164,20 +161,19 @@ test_expect_success 'log --graph with tricky octopus merge and its child, no col
 	test_cmp expect.uncolored actual
 '
 
-test_expect_failure 'log --graph with tricky octopus merge and its child with colors' '
+test_expect_success 'log --graph with tricky octopus merge and its child with colors' '
 	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
 	cat >expect.colors <<-\EOF &&
 	* left
 	<RED>|<RESET> * after-merge
-	<RED>|<RESET> *<MAGENTA>-<RESET><MAGENTA>-<RESET><CYAN>-<RESET><CYAN>.<RESET>   octopus-merge
-	<RED>|<RESET> <RED>|<RESET><BLUE>\<RESET> <MAGENTA>\<RESET> <CYAN>\<RESET>
-	<RED>|<RESET><RED>/<RESET> <BLUE>/<RESET> <MAGENTA>/<RESET> <CYAN>/<RESET>
+	<RED>|<RESET> *<CYAN>-<RESET><CYAN>.<RESET>   octopus-merge
+	<RED>|<RESET><RED>/<RESET><BLUE>|<RESET><MAGENTA>\<RESET> <CYAN>\<RESET>
 	<RED>|<RESET> <BLUE>|<RESET> <MAGENTA>|<RESET> * 4
 	<RED>|<RESET> <BLUE>|<RESET> * <CYAN>|<RESET> 3
 	<RED>|<RESET> <BLUE>|<RESET> <CYAN>|<RESET><CYAN>/<RESET>
-	<RED>|<RESET> * <CYAN>|<RESET> 2
+	<RED>|<RESET> * <CYAN>/<RESET> 2
 	<RED>|<RESET> <CYAN>|<RESET><CYAN>/<RESET>
-	* <CYAN>|<RESET> 1
+	* <CYAN>/<RESET> 1
 	<CYAN>|<RESET><CYAN>/<RESET>
 	* initial
 	EOF
@@ -209,7 +205,7 @@ test_expect_success 'log --graph with crossover in octopus merge, no color' '
 	test_cmp expect.uncolored actual
 '
 
-test_expect_failure 'log --graph with crossover in octopus merge with colors' '
+test_expect_success 'log --graph with crossover in octopus merge with colors' '
 	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
 	cat >expect.colors <<-\EOF &&
 	* after-4
@@ -257,7 +253,7 @@ test_expect_success 'log --graph with crossover in octopus merge and its child,
 	test_cmp expect.uncolored actual
 '
 
-test_expect_failure 'log --graph with crossover in octopus merge and its child with colors' '
+test_expect_success 'log --graph with crossover in octopus merge and its child with colors' '
 	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
 	cat >expect.colors <<-\EOF &&
 	* after-4
@@ -353,7 +349,7 @@ test_expect_success 'log --graph with unrelated commit and octopus child, no col
 	test_cmp expect.uncolored actual
 '
 
-test_expect_failure 'log --graph with unrelated commit and octopus child with colors' '
+test_expect_success 'log --graph with unrelated commit and octopus child with colors' '
 	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
 	cat >expect.colors <<-\EOF &&
 	* after-initial
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
new file mode 100755
index 0000000000..18709a723e
--- /dev/null
+++ b/t/t4215-log-skewed-merges.sh
@@ -0,0 +1,243 @@
+#!/bin/sh
+
+test_description='git log --graph of skewed merges'
+
+. ./test-lib.sh
+
+check_graph () {
+	cat >expect &&
+	git log --graph --pretty=tformat:%s "$@" >actual.raw &&
+	sed "s/ *$//" actual.raw >actual &&
+	test_cmp expect actual
+}
+
+test_expect_success 'log --graph with merge fusing with its left and right neighbors' '
+	git checkout --orphan _p &&
+	test_commit A &&
+	test_commit B &&
+	git checkout -b _q @^ && test_commit C &&
+	git checkout -b _r @^ && test_commit D &&
+	git checkout _p && git merge --no-ff _q _r -m E &&
+	git checkout _r && test_commit F &&
+	git checkout _p && git merge --no-ff _r -m G &&
+	git checkout @^^ && git merge --no-ff _p -m H &&
+
+	check_graph <<-\EOF
+	*   H
+	|\
+	| *   G
+	| |\
+	| | * F
+	| * | E
+	|/|\|
+	| | * D
+	| * | C
+	| |/
+	* / B
+	|/
+	* A
+	EOF
+'
+
+test_expect_success 'log --graph with left-skewed merge' '
+	git checkout --orphan 0_p && test_commit 0_A &&
+	git checkout -b 0_q 0_p && test_commit 0_B &&
+	git checkout -b 0_r 0_p &&
+	test_commit 0_C &&
+	test_commit 0_D &&
+	git checkout -b 0_s 0_p && test_commit 0_E &&
+	git checkout -b 0_t 0_p && git merge --no-ff 0_r^ 0_s -m 0_F &&
+	git checkout 0_p && git merge --no-ff 0_s -m 0_G &&
+	git checkout @^ && git merge --no-ff 0_q 0_r 0_t 0_p -m 0_H &&
+
+	check_graph <<-\EOF
+	*-----.   0_H
+	|\ \ \ \
+	| | | | * 0_G
+	| |_|_|/|
+	|/| | | |
+	| | | * | 0_F
+	| |_|/|\|
+	|/| | | |
+	| | | | * 0_E
+	| |_|_|/
+	|/| | |
+	| | * | 0_D
+	| | |/
+	| | * 0_C
+	| |/
+	|/|
+	| * 0_B
+	|/
+	* 0_A
+	EOF
+'
+
+test_expect_success 'log --graph with nested left-skewed merge' '
+	git checkout --orphan 1_p &&
+	test_commit 1_A &&
+	test_commit 1_B &&
+	test_commit 1_C &&
+	git checkout -b 1_q @^ && test_commit 1_D &&
+	git checkout 1_p && git merge --no-ff 1_q -m 1_E &&
+	git checkout -b 1_r @~3 && test_commit 1_F &&
+	git checkout 1_p && git merge --no-ff 1_r -m 1_G &&
+	git checkout @^^ && git merge --no-ff 1_p -m 1_H &&
+
+	check_graph <<-\EOF
+	*   1_H
+	|\
+	| *   1_G
+	| |\
+	| | * 1_F
+	| * | 1_E
+	|/| |
+	| * | 1_D
+	* | | 1_C
+	|/ /
+	* / 1_B
+	|/
+	* 1_A
+	EOF
+'
+
+test_expect_success 'log --graph with nested left-skewed merge following normal merge' '
+	git checkout --orphan 2_p &&
+	test_commit 2_A &&
+	test_commit 2_B &&
+	test_commit 2_C &&
+	git checkout -b 2_q @^^ &&
+	test_commit 2_D &&
+	test_commit 2_E &&
+	git checkout -b 2_r @^ && test_commit 2_F &&
+	git checkout 2_q &&
+	git merge --no-ff 2_r -m 2_G &&
+	git merge --no-ff 2_p^ -m 2_H &&
+	git checkout -b 2_s @^^ && git merge --no-ff 2_q -m 2_J &&
+	git checkout 2_p && git merge --no-ff 2_s -m 2_K &&
+
+	check_graph <<-\EOF
+	*   2_K
+	|\
+	| *   2_J
+	| |\
+	| | *   2_H
+	| | |\
+	| | * | 2_G
+	| |/| |
+	| | * | 2_F
+	| * | | 2_E
+	| |/ /
+	| * | 2_D
+	* | | 2_C
+	| |/
+	|/|
+	* | 2_B
+	|/
+	* 2_A
+	EOF
+'
+
+test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge' '
+	git checkout --orphan 3_p &&
+	test_commit 3_A &&
+	git checkout -b 3_q &&
+	test_commit 3_B &&
+	test_commit 3_C &&
+	git checkout -b 3_r @^ &&
+	test_commit 3_D &&
+	git checkout 3_q && git merge --no-ff 3_r -m 3_E &&
+	git checkout 3_p && git merge --no-ff 3_q -m 3_F &&
+	git checkout 3_r && test_commit 3_G &&
+	git checkout 3_p && git merge --no-ff 3_r -m 3_H &&
+	git checkout @^^ && git merge --no-ff 3_p -m 3_J &&
+
+	check_graph <<-\EOF
+	*   3_J
+	|\
+	| *   3_H
+	| |\
+	| | * 3_G
+	| * | 3_F
+	|/| |
+	| * | 3_E
+	| |\|
+	| | * 3_D
+	| * | 3_C
+	| |/
+	| * 3_B
+	|/
+	* 3_A
+	EOF
+'
+
+test_expect_success 'log --graph with right-skewed merge following a left-skewed one' '
+	git checkout --orphan 4_p &&
+	test_commit 4_A &&
+	test_commit 4_B &&
+	test_commit 4_C &&
+	git checkout -b 4_q @^^ && test_commit 4_D &&
+	git checkout -b 4_r 4_p^ && git merge --no-ff 4_q -m 4_E &&
+	git checkout -b 4_s 4_p^^ &&
+	git merge --no-ff 4_r -m 4_F &&
+	git merge --no-ff 4_p -m 4_G &&
+	git checkout @^^ && git merge --no-ff 4_s -m 4_H &&
+
+	check_graph --date-order <<-\EOF
+	*   4_H
+	|\
+	| *   4_G
+	| |\
+	| * | 4_F
+	|/| |
+	| * |   4_E
+	| |\ \
+	| | * | 4_D
+	| |/ /
+	|/| |
+	| | * 4_C
+	| |/
+	| * 4_B
+	|/
+	* 4_A
+	EOF
+'
+
+test_expect_success 'log --graph with octopus merge with column joining its penultimate parent' '
+	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 &&
+
+	check_graph <<-\EOF
+	*   5_H
+	|\
+	| *-.   5_G
+	| |\ \
+	| | | * 5_F
+	| | * |   5_E
+	| |/|\ \
+	| |_|/ /
+	|/| | /
+	| | |/
+	* | | 5_D
+	| | * 5_C
+	| |/
+	|/|
+	| * 5_B
+	|/
+	* 5_A
+	EOF
+'
+
+test_done
diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh
index f7181d1d6a..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,9 +148,8 @@ test_expect_success '--graph --full-history -- bar.txt' '
 	echo "|\\  " >> expected &&
 	echo "| * $C4" >> expected &&
 	echo "* | $A5" >> expected &&
-	echo "* |   $A4" >> expected &&
-	echo "|\\ \\  " >> expected &&
-	echo "| |/  " >> expected &&
+	echo "* | $A4" >> expected &&
+	echo "|\\| " >> expected &&
 	echo "* | $A3" >> expected &&
 	echo "|/  " >> expected &&
 	echo "* $A2" >> expected &&
@@ -255,7 +251,7 @@ test_expect_success '--graph --boundary ^C3' '
 	echo "* | | | $A3" >> expected &&
 	echo "o | | | $A2" >> expected &&
 	echo "|/ / /  " >> expected &&
-	echo "o | | $A1" >> expected &&
+	echo "o / / $A1" >> expected &&
 	echo " / /  " >> expected &&
 	echo "| o $C3" >> expected &&
 	echo "|/  " >> expected &&