Assertion in git log graphing

Assertion in git log graphing

[Bradley Smith]

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

Re: Assertion in git log graphing [regression in v2.25]

[Jeff King]

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

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

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.

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

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

Re: Assertion in git log graphing [regression in v2.25]

[Derrick Stolee]

On 1/7/2020 6:48 AM, Jeff King wrote:
> On Tue, Jan 07, 2020 at 11:24:50AM +0000, Bradley Smith wrote:
> 
>> 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.
> 
> 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.
> 
>> 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):
> 
> 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.

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

Re: Assertion in git log graphing [regression in v2.25]

[Derrick Stolee]

On 1/7/2020 7:22 AM, Derrick Stolee wrote:
> I'm also going to take a look this morning, starting by creating a test.

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

diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 18709a723e..bab8a7ed56 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -240,4 +240,47 @@ test_expect_success 'log --graph with octopus merge with column joining its penu
 	EOF
 '
 
+test_expect_failure 'log --graph with multiple tips' '
+	git checkout --orphan 6_1 &&
+	test_commit 6_A &&
+	git branch 6_2 &&
+	git branch 6_4 &&
+	test_commit 6_B &&
+	git branch 6_3 &&
+	test_commit 6_C &&
+	git checkout 6_2 && test_commit 6_D &&
+	git checkout 6_3 && test_commit 6_E &&
+	git checkout -b 6_5 6_1 &&
+	git merge --no-ff 6_2 -m 6_F &&
+	git checkout 6_4 && test_commit 6_G &&
+	git checkout 6_3 &&
+	git merge --no-ff 6_4 -m 6_H &&
+	git checkout 6_1 &&
+	git merge --no-ff 6_2 -m 6_I &&
+
+	check_graph 6_1 6_3 6_5 <<-\EOF
+	* 6_I
+	|\
+	| | * 6_H
+	| | |\
+	| | | * 6_G
+	| | * | 6_E
+	| | | | *   6_F
+	| | | | |\
+	| |_|_|/ /
+	|/| | | /
+	| | |_|/
+	| |/| |
+	| * | | 6_D
+	| | |/
+	| |/|
+	* | | 6_C
+	| |/
+	|/|
+	* | 6_B
+	|/
+	* 6_A
+	EOF
+'
+
 test_done
-- 
2.24.1.vfs.1.1.12.gccc87aa318

Re: Assertion in git log graphing [regression in v2.25]

[Eric Sunshine]

On Tue, Jan 7, 2020 at 7:42 AM Derrick Stolee <stolee@gmail.com> wrote:
> Here is a a patch that reproduces the test failure. It hits the
> assert, so it definitely fails.

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.

Re: Assertion in git log graphing [regression in v2.25]

[Derrick Stolee]

On 1/7/2020 7:50 AM, Eric Sunshine wrote:
> On Tue, Jan 7, 2020 at 7:42 AM Derrick Stolee <stolee@gmail.com> wrote:
>> Here is a a patch that reproduces the test failure. It hits the
>> assert, so it definitely fails.
> 
> 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.

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

Re: Assertion in git log graphing [regression in v2.25]

[Eric Sunshine]

On Tue, Jan 7, 2020 at 7:56 AM Derrick Stolee <stolee@gmail.com> wrote:
> On 1/7/2020 7:50 AM, Eric Sunshine wrote:
> > On Tue, Jan 7, 2020 at 7:42 AM Derrick Stolee <stolee@gmail.com> wrote:
> >> Here is a a patch that reproduces the test failure. It hits the
> >> assert, so it definitely fails.
> >
> > 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.
>
> A final version of the patch would probably fix the bug and not use
> test_expect_failure.

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

Re: Assertion in git log graphing [regression in v2.25]

[Derrick Stolee]

On 1/7/2020 6:48 AM, Jeff King wrote:
> The assertion itself is quite old, so I wondered if it was even still
> relevant. Removing it does produce a reasonable-looking graph:

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:

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

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:

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

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

Re: Assertion in git log graphing [regression in v2.25]

[Jeff King]

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

> On 1/7/2020 6:48 AM, Jeff King wrote:
> > The assertion itself is quite old, so I wondered if it was even still
> > relevant. Removing it does produce a reasonable-looking graph:
> 
> 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:

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

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

> >   | | | | * dd068b4 Merge commit '8f076d8' into HEAD
> >   | |_|_|/| 
> >   |/| | |/  
> >   | | |/|   
> >   | |/| |   
> >   | * | | 8f076d8 5
> 
> 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:
> 
> >   | | | | * dd068b4 Merge commit '8f076d8' into HEAD
> >   | |_|_|/| 
> >   |/| |_|/  
> >   | |/| |   
> >   | * | | 8f076d8 5
> 
> Note that I dropped a line and compressed a slash into an underscore. It's
> on that line that this condition is being hit.

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

Re: Assertion in git log graphing [regression in v2.25]

[Derrick Stolee]

On 1/7/2020 9:04 AM, Jeff King wrote:
> On Tue, Jan 07, 2020 at 08:25:59AM -0500, Derrick Stolee wrote:
> 
>> On 1/7/2020 6:48 AM, Jeff King wrote:
>>> The assertion itself is quite old, so I wondered if it was even still
>>> relevant. Removing it does produce a reasonable-looking graph:
>>
>> 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:
> 
> Oh, you're right. I totally missed that.
> 
> So perhaps we have two bugs, or perhaps they have the same root cause.
> 
>>>   | | | | * dd068b4 Merge commit '8f076d8' into HEAD
>>>   | |_|_|/| 
>>>   |/| | |/  
>>>   | | |/|   
>>>   | |/| |   
>>>   | * | | 8f076d8 5
>>
>> 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:
>>
>>>   | | | | * dd068b4 Merge commit '8f076d8' into HEAD
>>>   | |_|_|/| 
>>>   |/| |_|/  
>>>   | |/| |   
>>>   | * | | 8f076d8 5
>>
>> Note that I dropped a line and compressed a slash into an underscore. It's
>> on that line that this condition is being hit.
> 
> 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.
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

Re: Assertion in git log graphing [regression in v2.25]

[Derrick Stolee]

On 1/7/2020 9:22 AM, Derrick Stolee wrote:
> 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

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

Re: Assertion in git log graphing

[Derrick Stolee]

On 1/7/2020 6:24 AM, Bradley Smith wrote:
> 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.

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/