patch, 2 partsgraph: add test to demonstrate horizontal line bug

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

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(+)

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(-)

On Wed, Jan 08, 2020 at 04:27:55AM +0000, Derrick Stolee via GitGitGadget 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.

-Peff

On 1/8/2020 2:25 AM, Jeff King wrote:

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

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

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

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

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.

On 1/8/2020 1:06 PM, Junio C Hamano wrote:

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

Derrick Stolee <stolee@gmail.com> writes:

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

Thanks.