Assertion in git log graphing

Hi,

The following git repository (https://github.com/brads55/git-testcase) causes an assertion when running:

  $ git log --oneline --graph --all

  git-log: graph.c:1228: graph_output_collapsing_line: Assertion
`graph->mapping[i - 3] == target' failed.

The assertion seems to be caused by commit 0f0f389f12029b1c3745f8ed7aacfe6b2fc7a6cc. The graph structure of the above repository is as follows (as produced by v2.24.1):

*   a0a130c Merge commit '8f076d8' into HEAD
|\
| | *   f0f3be5 Merge commit '1b4b8d0' into HEAD
| | |\
| | | * 1b4b8d0 6
| | * | 2c44f1b 2
| | | | *   dd068b4 Merge commit '8f076d8' into HEAD
| | | | |\
| |_|_|/ /
|/| | | /
| | |_|/
| |/| |
| * | | 8f076d8 5
| | |/
| |/|
* | | a261135 4
| |/
|/|
* | a267dd6 1
|/
* 68f4772 0

Regards, Bradley Smith

On Tue, Jan 07, 2020 at 11:24:50AM +0000, Bradley Smith wrote:

Thanks for the report, and especially for providing a reproduction case!

The problem is new in the v2.25 release candidates, so we should try to deal with it before the release.

Yeah, I can confirm that this introduces the problem. I admit to not following the recent graph changes too closely, so I'll add James to the cc for attention.

The assertion itself is quite old, so I wondered if it was even still relevant. Removing it does produce a reasonable-looking graph:

  *   a0a130c Merge commit '8f076d8' into HEAD
  |\  
  | | *   f0f3be5 Merge commit '1b4b8d0' into HEAD
  | | |\  
  | | | * 1b4b8d0 6
  | | * | 2c44f1b 2
  | | | | * dd068b4 Merge commit '8f076d8' into HEAD
  | |_|_|/| 
  |/| | |/  
  | | |/|   
  | |/| |   
  | * | | 8f076d8 5
  | | |/  
  | |/|   
  * | | a261135 4
  | |/  
  |/|   
  * | a267dd6 1
  |/  
  * 68f4772 0

but the colors aren't quite right. In particular, in this segment:

    | | | | * dd068b4 Merge commit '8f076d8' into HEAD
    | |_|_|/| 
    |/| | |/  

the first-parent line coming from dd068b4 is red in the slashes, but uncolored in the underscores.

So much for naive fix. :)

-Peff

On 1/7/2020 6:48 AM, Jeff King wrote:

I'm also going to take a look this morning, starting by creating a test. I reviewed what I could of James' patch series, but I was also unfamiliar with graph.c and relied on his very substantial test cases to verify the correctness. Looks like a corner case got missed.

Thanks, -Stolee

On 1/7/2020 7:22 AM, Derrick Stolee wrote:

Here is a a patch that reproduces the test failure. It hits the assert, so it definitely fails.

NOTE: The test may not actually pass after this bug is fixed, as
the output expectation may not match exactly. Thus, the test will
likely still fail after fixing the bug, but for a different reason.
I could use the output from v2.24.1, but the point of these changes
in graph.c was to have a compressed output in exactly these cases
of multiple edges moving to the left. In particular, the edges out
of 6_F will likely need updating.

If I manage to do the "right" fix, then I'll update this test accordingly.

-Stolee

-->8--

From: Derrick Stolee <dstolee@microsoft.com>
Date: Tue, 7 Jan 2020 07:35:56 -0500
Subject: [PATCH] graph: add failing test that hits assert()

A failure was reported in "git log --graph --all" with the new graph-rendering logic. Create a test case that matches the topology of that example and uses an explicit ref ordering instead of the "--all" option. The test fails with the following error:

	graph.c:1228: graph_output_collapsing_line: Assertion
		      `graph->mapping[i - 3] == target' failed.

Reported-by: Bradley Smith <brad@brad-smith.co.uk>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 t/t4215-log-skewed-merges.sh | 43 ++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)

On Tue, Jan 7, 2020 at 7:42 AM Derrick Stolee <stolee@gmail.com> wrote:

What happens if someone builds the project with NDEBUG? Then the test won't fail as expected. Perhaps this patch ought to also change those asserts() to `if (...) BUG(...)` to ensure consistent behavior.

On 1/7/2020 7:50 AM, Eric Sunshine wrote:

A final version of the patch would probably fix the bug and not use test_expect_failure. The other option would be to replace every assert() with a macro that did the "if (...) BUG(...);" conversion, but maybe that's not necessary in general.

-Stolee

On Tue, Jan 7, 2020 at 7:56 AM Derrick Stolee <stolee@gmail.com> wrote:

Indeed, I understood that when I made the suggestion, but you still want to be able to catch the problem if the code ever regresses and reintroduces the bug. And, to do so, you'd want to ensure consistent behavior which you get with BUG() but not with assert().

On 1/7/2020 6:48 AM, Jeff King wrote:

As I'm digging into this case, and finding when the assertion is hit, I see that the issue is in the line further below your coloring issue:

What is output is actually this, above. But the logic that includes the assert is checking where the underscores end, and the shown underscores actually pass the check. The issue is that it seems like it really wants to show this:

Note that I dropped a line and compressed a slash into an underscore. It's on that line that this condition is being hit.

Now, is this really the intended behavior? Maybe. Looking at the previous tests in 54125-log-skewed-merges.sh, I don't see any where we have two skewed merges in the same merge.

Thanks, -Stolee

On Tue, Jan 07, 2020 at 08:25:59AM -0500, Derrick Stolee wrote:

Oh, you're right. I totally missed that.

So perhaps we have two bugs, or perhaps they have the same root cause.

Hrm. I could see either being acceptable, but I do think the second one is a bit easier to read. I'm not sure which was intended for this case.

-Peff

On 1/7/2020 9:04 AM, Jeff King wrote:

Somewhat expanding the situation to test more of these collapses, I can get the following graph:

*   6_M1
|\
| | *   6_M2
| | |\
| | | * 6_H
| | | | *   6_M3
| | | | |\
| | | | | * 6_J
| | | | * | 6_I
| | | | | | *   6_M4
| |_|_|_|_|/|\
|/| | | | |/ /
| | | | |/| /
| | | |/| |/
| | |/| |/|
| |/| |/| |
| | |/| | |
| | * | | | 6_G
| | | |_|/
| | |/| |
| | * | | 6_F
| * | | | 6_E
| | |/ /
| |/| |
| * | | 6_D
| | |/
| |/|
* | | 6_C
| |/
|/|
* | 6_B
|/
* 6_A

Note how 6_M4 has three parents, and the first parent has a horizontal edge. Even giving an extra padding line between horizontal edges, we _could_ output the following instead:

| | | | | | *   6_M4
| |_|_|_|_|/|\
|/| | | | |/ /
| | |_|_|/| /
| |/| | | |/
| | | |_|/|
| | |/| | |
| | * | | | 6_G

However, I'll stick with the fix for the coloring issue. I think it was a previous bug that just wasn't hit until now.

Thanks, -Stolee

On 1/7/2020 9:22 AM, Derrick Stolee wrote:

I should have tested this example with v2.24.1, which gives this output in this section:

| | | | | | *-.   6_M4
| | | | | | |\ \  
| |_|_|_|_|/ / /  
|/| | | | | / /   
| | |_|_|_|/ /    
| |/| | | | /     
| | | |_|_|/      
| | |/| | |       
| | * | | | 6_G

So, this is likely the behavior we would prefer.

For the release, it is likely best to keep the change that does not collapse properly and fix this collapse bug later. (It is likely an invasive change.)

Thanks, -Stolee

On 1/7/2020 6:24 AM, Bradley Smith wrote:

Bradley,

Thanks for the report. I've submitted [1] what I hope to be a sufficient fix.

Thanks, -Stolee

[1] https://lore.kernel.org/git/pull.517.git.1578408947.gitgitgadget@gmail.com/