diff mbox series

[1/3] graph: fix case that hit assert()

Message ID 65186f3ded251e0bcf1fcb18160163a3efd97c37.1578408947.git.gitgitgadget@gmail.com (mailing list archive)
State New, archived
Headers show
Series Fix two bugs in graph.c | expand

Commit Message

Johannes Schindelin via GitGitGadget Jan. 7, 2020, 2:55 p.m. UTC 
From: Derrick Stolee <dstolee@microsoft.com>

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 would fail with the following error:

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

The situation is a little complicated, so let's break it down.

The assert was introduced by eaf158f8 ("graph API: Use horizontal
lines for more compact graphs", 2009-04-21), which is quite old.
This assert is trying to say that when we complete a horizontal
line with a single slash, it is because we have reached our target.

This assertion is hit when we have two collapsing lines from the
same merge commit, as follows:

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

It is actually the _second_ collapsing line that hits this assert.
The reason we are in this code path is because we are collapsing
the first line, and it in that case we are hitting our target now
that the horizontal line is complete. However, the second line
cannot be a horizontal line, so it will collapse without horizontal
lines. In this case, it is inappropriate to assert that we have
reached our target, as we need to continue for another column
before reaching the target. Dropping the assert is safe here.

Second, the horizontal lines in that first line drop their coloring.
This is due to a use of graph_line_addch() instead of
graph_line_write_column(). Using a ternary operator to pick the
character is nice for compact code, but we actually need a column
to provide the color.

Helped-by: Jeff King <peff@peff.net>
Reported-by: Bradley Smith <brad@brad-smith.co.uk>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 graph.c                      | 17 ++++++++-------
 t/t4215-log-skewed-merges.sh | 42 ++++++++++++++++++++++++++++++++++++
 2 files changed, 51 insertions(+), 8 deletions(-)

Comments

Jeff King Jan. 7, 2020, 3:30 p.m. UTC | #1 
On Tue, Jan 07, 2020 at 02:55:45PM +0000, Derrick Stolee via GitGitGadget wrote:

> From: Derrick Stolee <dstolee@microsoft.com>
> 
> 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 would fail with the following error:
> 
> 	graph.c:1228: graph_output_collapsing_line: Assertion
> 		      `graph->mapping[i - 3] == target' failed.
> 
> The situation is a little complicated, so let's break it down.

First off, thanks for digging into this so promptly. Your solution looks
correct to me. Everything else I'll mention here are nits. :)

Your commit message starts off talking about the test, but without
describing what's interesting about it. I think the answer is that we
have two "skewed" merge parents for the same merge; maybe it would make
sense to lead with that. I.e.:

  Subject: graph: drop assert() for merge with two collapsing parents

  When "git log --graph" shows a merge commit that has two collapsing
  lines, like:

    [your diagram]

  we trigger an assert():

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

  ...and so on...

> The assert was introduced by eaf158f8 ("graph API: Use horizontal
> lines for more compact graphs", 2009-04-21), which is quite old.
> This assert is trying to say that when we complete a horizontal
> line with a single slash, it is because we have reached our target.

Thanks for this final sentence; writing that out in English made the
purpose of the assert() much clearer.

That could perhaps be an argument in favor of writing it as a BUG()
with a similar human-readable explanation. I guess there was already a
comment in the code, but it didn't quite click with me as much as what
you wrote above.

> It is actually the _second_ collapsing line that hits this assert.
> The reason we are in this code path is because we are collapsing
> the first line, and it in that case we are hitting our target now

s/it//

> that the horizontal line is complete. However, the second line
> cannot be a horizontal line, so it will collapse without horizontal
> lines. In this case, it is inappropriate to assert that we have
> reached our target, as we need to continue for another column
> before reaching the target. Dropping the assert is safe here.

I think that makes sense. My big concern here is that the assert() was
preventing us from looking out of bounds in the graph->mapping array,
but I don't think that's the case here.

Worth mentioning that this was due to 0f0f389f12 (graph: tidy up display
of left-skewed merges, 2019-10-15), in case somebody has to later dig
deeper?

> Second, the horizontal lines in that first line drop their coloring.
> This is due to a use of graph_line_addch() instead of
> graph_line_write_column(). Using a ternary operator to pick the
> character is nice for compact code, but we actually need a column
> to provide the color.

It seems like this is a totally separate bug, and could be its own
commit?

I think it's also caused by 0f0f389f12, which actually introduced the
seen_parent mechanism that you're correcting here.

> Helped-by: Jeff King <peff@peff.net>
> Reported-by: Bradley Smith <brad@brad-smith.co.uk>

I don't know that I did much, but OK. :)

Thanks once again Bradley for the reproducible case.

> diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
> index 18709a723e..ddf6f6f5d3 100755
> --- a/t/t4215-log-skewed-merges.sh
> +++ b/t/t4215-log-skewed-merges.sh
> @@ -240,4 +240,46 @@ test_expect_success 'log --graph with octopus merge with column joining its penu
>  	EOF
>  '
>  
> +test_expect_success 'log --graph with multiple tips' '

This nicely covers the assert() problem. Could we check the same case
with "--color" and test_decode_color to check the coloring issue (see
t4214 for some prior art)?

-Peff
Derrick Stolee Jan. 7, 2020, 6:47 p.m. UTC | #2 
On 1/7/2020 10:30 AM, Jeff King wrote:
> On Tue, Jan 07, 2020 at 02:55:45PM +0000, Derrick Stolee via GitGitGadget wrote:
> 
>> From: Derrick Stolee <dstolee@microsoft.com>
>>
>> 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 would fail with the following error:
>>
>> 	graph.c:1228: graph_output_collapsing_line: Assertion
>> 		      `graph->mapping[i - 3] == target' failed.
>>
>> The situation is a little complicated, so let's break it down.
> 
> First off, thanks for digging into this so promptly. Your solution looks
> correct to me. Everything else I'll mention here are nits. :)
> 
> Your commit message starts off talking about the test, but without
> describing what's interesting about it. I think the answer is that we
> have two "skewed" merge parents for the same merge; maybe it would make
> sense to lead with that. I.e.:
> 
>   Subject: graph: drop assert() for merge with two collapsing parents
> 
>   When "git log --graph" shows a merge commit that has two collapsing
>   lines, like:
> 
>     [your diagram]
> 
>   we trigger an assert():
> 
>     graph.c:1228: graph_output_collapsing_line: Assertion
>                   `graph->mapping[i - 3] == target' failed.
> 
>   ...and so on...

Good points.

>> The assert was introduced by eaf158f8 ("graph API: Use horizontal
>> lines for more compact graphs", 2009-04-21), which is quite old.
>> This assert is trying to say that when we complete a horizontal
>> line with a single slash, it is because we have reached our target.
> 
> Thanks for this final sentence; writing that out in English made the
> purpose of the assert() much clearer.
> 
> That could perhaps be an argument in favor of writing it as a BUG()
> with a similar human-readable explanation. I guess there was already a
> comment in the code, but it didn't quite click with me as much as what
> you wrote above.
> 
>> It is actually the _second_ collapsing line that hits this assert.
>> The reason we are in this code path is because we are collapsing
>> the first line, and it in that case we are hitting our target now
> 
> s/it//
> 
>> that the horizontal line is complete. However, the second line
>> cannot be a horizontal line, so it will collapse without horizontal
>> lines. In this case, it is inappropriate to assert that we have
>> reached our target, as we need to continue for another column
>> before reaching the target. Dropping the assert is safe here.
> 
> I think that makes sense. My big concern here is that the assert() was
> preventing us from looking out of bounds in the graph->mapping array,
> but I don't think that's the case here.
> 
> Worth mentioning that this was due to 0f0f389f12 (graph: tidy up display
> of left-skewed merges, 2019-10-15), in case somebody has to later dig
> deeper?

Can do.

>> Second, the horizontal lines in that first line drop their coloring.
>> This is due to a use of graph_line_addch() instead of
>> graph_line_write_column(). Using a ternary operator to pick the
>> character is nice for compact code, but we actually need a column
>> to provide the color.
> 
> It seems like this is a totally separate bug, and could be its own
> commit?
>
> I think it's also caused by 0f0f389f12, which actually introduced the
> seen_parent mechanism that you're correcting here.

You're right. These are better split. Any idea how to test the color?
(I'm pretty sure we have some tests for this... I can dig around.)
 
>> Helped-by: Jeff King <peff@peff.net>
>> Reported-by: Bradley Smith <brad@brad-smith.co.uk>
> 
> I don't know that I did much, but OK. :)
> 
> Thanks once again Bradley for the reproducible case.
> 
>> diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
>> index 18709a723e..ddf6f6f5d3 100755
>> --- a/t/t4215-log-skewed-merges.sh
>> +++ b/t/t4215-log-skewed-merges.sh
>> @@ -240,4 +240,46 @@ test_expect_success 'log --graph with octopus merge with column joining its penu
>>  	EOF
>>  '
>>  
>> +test_expect_success 'log --graph with multiple tips' '
> 
> This nicely covers the assert() problem. Could we check the same case
> with "--color" and test_decode_color to check the coloring issue (see
> t4214 for some prior art)?

Thanks for pointing me to existing color tests. I'll add one to my v2.

-Stolee
Junio C Hamano Jan. 7, 2020, 7:21 p.m. UTC | #3 
Jeff King <peff@peff.net> writes:

>> Second, the horizontal lines in that first line drop their coloring.
>> This is due to a use of graph_line_addch() instead of
>> graph_line_write_column(). Using a ternary operator to pick the
>> character is nice for compact code, but we actually need a column
>> to provide the color.
>
> It seems like this is a totally separate bug, and could be its own
> commit?

I think so.

And with that removed, all that remains would be a removal of the
assert() plus an additional test?

>> +test_expect_success 'log --graph with multiple tips' '
>
> This nicely covers the assert() problem. Could we check the same case
> with "--color" and test_decode_color to check the coloring issue (see
> t4214 for some prior art)?
Jeff King Jan. 7, 2020, 7:31 p.m. UTC | #4 
On Tue, Jan 07, 2020 at 11:21:00AM -0800, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> >> Second, the horizontal lines in that first line drop their coloring.
> >> This is due to a use of graph_line_addch() instead of
> >> graph_line_write_column(). Using a ternary operator to pick the
> >> character is nice for compact code, but we actually need a column
> >> to provide the color.
> >
> > It seems like this is a totally separate bug, and could be its own
> > commit?
> 
> I think so.
> 
> And with that removed, all that remains would be a removal of the
> assert() plus an additional test?

Yes, though note that the color thing is a v2.25 regression as well. So
we'd probably want both of them.

-Peff
Junio C Hamano Jan. 7, 2020, 8:21 p.m. UTC | #5 
Jeff King <peff@peff.net> writes:

> On Tue, Jan 07, 2020 at 11:21:00AM -0800, Junio C Hamano wrote:
>
>> Jeff King <peff@peff.net> writes:
>> 
>> >> Second, the horizontal lines in that first line drop their coloring.
>> >> This is due to a use of graph_line_addch() instead of
>> >> graph_line_write_column(). Using a ternary operator to pick the
>> >> character is nice for compact code, but we actually need a column
>> >> to provide the color.
>> >
>> > It seems like this is a totally separate bug, and could be its own
>> > commit?
>> 
>> I think so.
>> 
>> And with that removed, all that remains would be a removal of the
>> assert() plus an additional test?
>
> Yes, though note that the color thing is a v2.25 regression as well. So
> we'd probably want both of them.

Sure.  Those two would make perfect pair of commits to finish -rc2 with.

Thanks.
diff mbox series

Patch

diff --git a/graph.c b/graph.c
index 66ae18add8..aaf97069bd 100644
--- a/graph.c
+++ b/graph.c
@@ -1063,7 +1063,7 @@  static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 	int i, j;
 
 	struct commit_list *first_parent = first_interesting_parent(graph);
-	int seen_parent = 0;
+	struct column *parent_col = NULL;
 
 	/*
 	 * Output the post-merge row
@@ -1117,12 +1117,17 @@  static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 			graph_line_addch(line, ' ');
 		} else {
 			graph_line_write_column(line, col, '|');
-			if (graph->merge_layout != 0 || i != graph->commit_index - 1)
-				graph_line_addch(line, seen_parent ? '_' : ' ');
+			if (graph->merge_layout != 0 || i != graph->commit_index - 1) {
+				if (parent_col)
+					graph_line_write_column(
+						line, parent_col, '_');
+				else
+					graph_line_addch(line, ' ');
+			}
 		}
 
 		if (col_commit == first_parent->item)
-			seen_parent = 1;
+			parent_col = col;
 	}
 
 	/*
@@ -1219,13 +1224,9 @@  static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 			 *
 			 * The space just to the left of this
 			 * branch should always be empty.
-			 *
-			 * The branch to the left of that space
-			 * should be our eventual target.
 			 */
 			assert(graph->mapping[i - 1] > target);
 			assert(graph->mapping[i - 2] < 0);
-			assert(graph->mapping[i - 3] == target);
 			graph->mapping[i - 2] = target;
 			/*
 			 * Mark this branch as the horizontal edge to
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 18709a723e..ddf6f6f5d3 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -240,4 +240,46 @@  test_expect_success 'log --graph with octopus merge with column joining its penu
 	EOF
 '
 
+test_expect_success '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