[PATCH 0/2] Graph horizontal fix

[PATCH 0/2] Graph horizontal fix

[Derrick Stolee via GitGitGadget]

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/faa954fa-ccb9-b034-a39d-d2f0696826ea@gmail.com/T/#t
[2] 
https://lore.kernel.org/git/xmqqk1635gwu.fsf@gitster-ct.c.googlers.com/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

[PATCH 1/2] graph: add test to demonstrate horizontal line bug

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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:

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

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 t/t4215-log-skewed-merges.sh | 62 ++++++++++++++++++++++++++++++++++++
 1 file changed, 62 insertions(+)

diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 5661ed5881..099e4b89b4 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -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

[PATCH 2/2] graph: fix collapse of multiple edges

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 graph.c                      | 10 ++++++++--
 t/t4215-log-skewed-merges.sh |  2 +-
 2 files changed, 9 insertions(+), 3 deletions(-)

diff --git a/graph.c b/graph.c
index aaf97069bd..4fb25ad464 100644
--- a/graph.c
+++ b/graph.c
@@ -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;
+			}
 		}
 	}
 
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 099e4b89b4..1d0d3240ff 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -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

Re: [PATCH 2/2] graph: fix collapse of multiple edges

[Jeff King]

On Wed, Jan 08, 2020 at 04:27:55AM +0000, Derrick Stolee via GitGitGadget wrote:

> 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:
> 
> 	| | | | | | *
> 	| |_|_|_|_|/|\
> 	|/| | | | |/ /
> 	| | |_|_|/| /
> 	| |/| | | |/
> 	| | | |_|/|
> 	| | |/| | |

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

Re: [PATCH 2/2] graph: fix collapse of multiple edges

[Derrick Stolee]

On 1/8/2020 2:25 AM, Jeff King wrote:
> On Wed, Jan 08, 2020 at 04:27:55AM +0000, Derrick Stolee via GitGitGadget wrote:
> 
>> 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:
>>
>> 	| | | | | | *
>> 	| |_|_|_|_|/|\
>> 	|/| | | | |/ /
>> 	| | |_|_|/| /
>> 	| |/| | | |/
>> 	| | | |_|/|
>> 	| | |/| | |
> 
> 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.

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

Re: [PATCH 2/2] graph: fix collapse of multiple edges

[Jeff King]

On Wed, Jan 08, 2020 at 08:40:26AM -0500, Derrick Stolee wrote:

> > 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.
> 
> 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.

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

> If there was one more row to the example, then we would have:
> 
>            | | | | | * 6_F
>            | |_|_|_|/|
>            |/| | | |/
>            | | |_|/|
>            | |/| | |
>            | * | | | 6_D

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

Re: [PATCH 0/2] Graph horizontal fix

[Junio C Hamano]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> 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.

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.

>
> Thanks, -Stolee
>
> [1] 
> https://lore.kernel.org/git/faa954fa-ccb9-b034-a39d-d2f0696826ea@gmail.com/T/#t
> [2] 
> https://lore.kernel.org/git/xmqqk1635gwu.fsf@gitster-ct.c.googlers.com/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

Re: [PATCH 0/2] Graph horizontal fix

[Derrick Stolee]

On 1/8/2020 1:06 PM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>> 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.
> 
> 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.

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

Re: [PATCH 0/2] Graph horizontal fix

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

> I guess I was incomplete in my first example. The full horizontal behavior
> before 0f0f389f was
> ...
> This change brings the horizontal lines back.

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

Thanks.