Graph horizontal fix

This depends on ds/graph-assert-fix.

This is a non-critical (not needed for v2.25.0) response to the previous discussions [1] [2].

While working to resolve the fix for the assert() bug, I noticed this regression when multiple edges wanted to collapse with horizontal lines. It takes a reasonably large graph, but real projects are likely to demonstrate this behavior.

I arranged the series into two patches: 1. the (failing) test, and 2. the fix.

The fix commit includes some details about why the change to compress merge commits caused this regression, and why I feel relatively confident that this is a correct resolution.

Thanks, -Stolee

[1]
https://lore.kernel.org/git/[email protected]/T/#t
[2]
https://lore.kernel.org/git/[email protected]/T/#t

Derrick Stolee (2):
graph: add test to demonstrate horizontal line bug
graph: fix collapse of multiple edges

 graph.c                      | 10 ++++--
 t/t4215-log-skewed-merges.sh | 62 ++++++++++++++++++++++++++++++++++++
 2 files changed, 70 insertions(+), 2 deletions(-)

base-commit: aa2121af50498c7ea9d5c4c87f9dc66605bf772b
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-518%2Fderrickstolee%2Fgraph-horizontal-fix-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-518/derrickstolee/graph-horizontal-fix-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/518

gitgitgadget

From: Derrick Stolee <[email protected]>

A previous test in t4215-log-skewed-merges.sh was added to demonstrate exactly the topology of a reported failure in "git log --graph". While investigating the fix, we realized that multiple edges that could collapse with horizontal lines were not doing so.

Specifically, examine this section of the graph:

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

Document this behavior with a test. This behavior is new, as the behavior in v2.24.1 has the following output:

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

The behavior changed logically in 479db18b ("graph: smooth appearance of collapsing edges on commit lines", 2019-10-15), but was actually broken due to an assert() bug in 458152cc ("graph: example of graph output that can be simplified", 2019-10-15). A future change could modify this behavior to do the following instead:

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

---
 t/t4215-log-skewed-merges.sh | 62 ++++++++++++++++++++++++++++++++++++
 1 file changed, 62 insertions(+)

index 5661ed5881..099e4b89b4 100755
@@ -311,4 +311,66 @@ test_expect_success 'log --graph with multiple tips and colors' '
 	test_cmp expect.colors actual.colors
 '
 
+test_expect_failure 'log --graph with multiple tips' '
+	git checkout --orphan 7_1 &&
+	test_commit 7_A &&
+	test_commit 7_B &&
+	test_commit 7_C &&
+	git checkout -b 7_2 7_1~2 &&
+	test_commit 7_D &&
+	test_commit 7_E &&
+	git checkout -b 7_3 7_1~1 &&
+	test_commit 7_F &&
+	test_commit 7_G &&
+	git checkout -b 7_4 7_2~1 &&
+	test_commit 7_H &&
+	git checkout -b 7_5 7_1~2 &&
+	test_commit 7_I &&
+	git checkout -b 7_6 7_3~1 &&
+	test_commit 7_J &&
+	git checkout -b M_1 7_1 &&
+	git merge --no-ff 7_2 -m 7_M1 &&
+	git checkout -b M_3 7_3 &&
+	git merge --no-ff 7_4 -m 7_M2 &&
+	git checkout -b M_5 7_5 &&
+	git merge --no-ff 7_6 -m 7_M3 &&
+	git checkout -b M_7 7_1 &&
+	git merge --no-ff 7_2 7_3 -m 7_M4 &&
+
+	check_graph M_1 M_3 M_5 M_7 <<-\EOF
+	*   7_M1
+	|\
+	| | *   7_M2
+	| | |\
+	| | | * 7_H
+	| | | | *   7_M3
+	| | | | |\
+	| | | | | * 7_J
+	| | | | * | 7_I
+	| | | | | | *   7_M4
+	| |_|_|_|_|/|\
+	|/| | | | |/ /
+	| | |_|_|/| /
+	| |/| | | |/
+	| | | |_|/|
+	| | |/| | |
+	| | * | | | 7_G
+	| | | |_|/
+	| | |/| |
+	| | * | | 7_F
+	| * | | | 7_E
+	| | |/ /
+	| |/| |
+	| * | | 7_D
+	| | |/
+	| |/|
+	* | | 7_C
+	| |/
+	|/|
+	* | 7_B
+	|/
+	* 7_A
+	EOF
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

This fix resolves the previously-added test_expect_failure in t4215-log-skewed-merges.sh.

The issue lies in the "else" condition while updating the mapping inside graph_output_collapsing_line(). In 0f0f389f (graph: tidy up display of left-skewed merges, 2019-10-15), the output of left- skewed merges was changed to allow an immediate horizontal edge in the first parent, output by graph_output_post_merge_line() instead of by graph_output_collapsing_line(). This condensed the first line behavior as follows:

Before 0f0f389f:

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

After 0f0f389f:

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

However, a very subtle issue arose when the second and third parent edges are collapsed in later steps. The second parent edge is now immediately adjacent to a vertical edge. This means that the condition

	} else if (graph->mapping[i - 1] < 0) {

in graph_output_collapsing_line() evaluates as false. The block for this condition was the only place where we connected the target column with the current position with horizontal edge markers.

In this case, the final "else" block is run, and the edge is marked as horizontal, but did not back-fill the blank columns between the target and the current edge. Since the second parent edge is marked as horizontal, the third parent edge is not marked as horizontal. This causes the output to continue as follows:

Before this change:

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

By adding the logic for "filling" a horizontal edge between the target column and the current column, we are able to resolve the issue.

After this change:

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

This output properly matches the expected blend of the edge behavior before 0f0f389f and the merge commit rendering from 0f0f389f.

---
 graph.c                      | 10 ++++++++--
 t/t4215-log-skewed-merges.sh |  2 +-
 2 files changed, 9 insertions(+), 3 deletions(-)

index aaf97069bd..4fb25ad464 100644
@@ -1233,8 +1233,14 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 			 * prevent any other edges from moving
 			 * horizontally.
 			 */
-			if (horizontal_edge == -1)
-				horizontal_edge = i;
+			if (horizontal_edge == -1) {
+				int j;
+				horizontal_edge_target = target;
+				horizontal_edge = i - 1;
+
+				for (j = (target * 2) + 3; j < (i - 2); j += 2)
+					graph->mapping[j] = target;
+			}
 		}
 	}
 

index 099e4b89b4..1d0d3240ff 100755
@@ -311,7 +311,7 @@ test_expect_success 'log --graph with multiple tips and colors' '
 	test_cmp expect.colors actual.colors
 '
 
-test_expect_failure 'log --graph with multiple tips' '
+test_expect_success 'log --graph with multiple tips' '
 	git checkout --orphan 7_1 &&
 	test_commit 7_A &&
 	test_commit 7_B &&

gitgitgadget

Hmm. Your description and your diagrams make sense to me. But one curious thing is that the earlier test you added for 6_* does not need modified. Because it continues to show:

          | | | | * 6_F
          | |_|_|/|
          |/| | |/
          | | |/|
          | |/| |
          | * | | 6_D

rather than adding a horizontal component to the second-parent line. That seems inconsistent.

-Peff

The issue here is that there is not enough room for a second horizontal line. The horizontal line can only start after the previous has completely terminated, that is

           | | | | * 6_F
           | |_|_|/|
           |/| | |/

at this point, the first horizontal line has terminated.

           | | |/|
           | |/| |

The remaining movement for the second line has no room for a horizontal edge. The logic that I added is hit, but the for loop (over j) terminates immediately without a single execution of the loop body.

If there was one more row to the example, then we would have:

           | | | | | * 6_F
           | |_|_|_|/|
           |/| | | |/
           | | |_|/|
           | |/| | |
           | * | | | 6_D

Thanks,
-Stolee

Ahhh, OK, that makes perfect sense. I didn't quite realize how the rules for "going horizontal" worked.

Right, that makes sense. Thanks for explaining. And the patch otherwise looked good to me; your explanation convinced me that this is the right thing to do.

-Peff

I am not sure if this is "fix" of "bug" in that what is shown without 2/2 (iow, "before this change" in the description of 2/2) is "wrong" per-se---it is just that it leaves room to be made even more compact. It still is an improvement, of course, though.

Queued. Thanks.

I guess I was incomplete in my first example. The full horizontal behavior before 0f0f389f was

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

and 0f0f389f added a compact merge commit, but lost two horizontal lines.

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

This change brings the horizontal lines back.

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

Whether this qualifies as a "bug" is debatable, for sure. That's why I believe this change is below the bar for the release candidate.

Thanks,
-Stolee

Ah, I see. That was what you meant by regression-and-fix.

Thanks.