[PATCH 0/3] Fix two bugs in graph.c

[PATCH 0/3] Fix two bugs in graph.c

[Derrick Stolee via GitGitGadget]

This is a possible fix for the bug reported in [1].

The first commit fixes the runtime failure due to the assert() statement.

The second commit replaces the assert() statements with a macro that
triggers a BUG().

The third commit adds another test that shows a more complicated example and
how the new code in v2.25.0-rc1 has a behavior change that is not
necessarily wanted.

Thanks, -Stolee

[1] 
https://lore.kernel.org/git/CAHt=fUXTHc4JPsapvHKnw5vHhp2cBOYRNfdaSDWBUnKt8fWfeA@mail.gmail.com/

Derrick Stolee (3):
  graph: fix case that hit assert()
  graph: replace assert() with graph_assert() macro
  t4215: add bigger graph collapse test

 graph.c                      |  39 +++++++------
 t/t4215-log-skewed-merges.sh | 105 +++++++++++++++++++++++++++++++++++
 2 files changed, 126 insertions(+), 18 deletions(-)


base-commit: 8679ef24ed64018bb62170c43ce73e0261c0600a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-517%2Fderrickstolee%2Fgraph-assert-fix-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-517/derrickstolee/graph-assert-fix-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/517
-- 
gitgitgadget

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

[Derrick Stolee via GitGitGadget]

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

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

[PATCH 2/3] graph: replace assert() with graph_assert() macro

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

The assert() macro is sometimes compiled out. Instead, switch these into
BUG() statements using our own custom macro.

Reported-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 graph.c | 22 ++++++++++++----------
 1 file changed, 12 insertions(+), 10 deletions(-)

diff --git a/graph.c b/graph.c
index aaf97069bd..ac78bdf96c 100644
--- a/graph.c
+++ b/graph.c
@@ -6,6 +6,8 @@
 #include "revision.h"
 #include "argv-array.h"
 
+#define graph_assert(exp) if (!(exp)) { BUG("assert failed: "#exp""); }
+
 /* Internal API */
 
 /*
@@ -316,7 +318,7 @@ static struct strbuf *diff_output_prefix_callback(struct diff_options *opt, void
 	struct git_graph *graph = data;
 	static struct strbuf msgbuf = STRBUF_INIT;
 
-	assert(opt);
+	graph_assert(opt);
 
 	strbuf_reset(&msgbuf);
 	if (opt->line_prefix)
@@ -865,13 +867,13 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 	 *
 	 * We need 2 extra rows for every parent over 2.
 	 */
-	assert(graph->num_parents >= 3);
+	graph_assert(graph->num_parents >= 3);
 
 	/*
 	 * graph->expansion_row tracks the current expansion row we are on.
 	 * It should be in the range [0, num_expansion_rows - 1]
 	 */
-	assert(0 <= graph->expansion_row &&
+	graph_assert(0 <= graph->expansion_row &&
 	       graph->expansion_row < graph_num_expansion_rows(graph));
 
 	/*
@@ -923,13 +925,13 @@ static void graph_output_commit_char(struct git_graph *graph, struct graph_line
 	 * (We should only see boundary commits when revs->boundary is set.)
 	 */
 	if (graph->commit->object.flags & BOUNDARY) {
-		assert(graph->revs->boundary);
+		graph_assert(graph->revs->boundary);
 		graph_line_addch(line, 'o');
 		return;
 	}
 
 	/*
-	 * get_revision_mark() handles all other cases without assert()
+	 * get_revision_mark() handles all other cases without graph_assert()
 	 */
 	graph_line_addstr(line, get_revision_mark(graph->revs, graph->commit));
 }
@@ -1094,7 +1096,7 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 
 			for (j = 0; j < graph->num_parents; j++) {
 				par_column = graph_find_new_column_by_commit(graph, parents->item);
-				assert(par_column >= 0);
+				graph_assert(par_column >= 0);
 
 				c = merge_chars[idx];
 				graph_line_write_column(line, &graph->new_columns[par_column], c);
@@ -1172,14 +1174,14 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 		 * the graph much more legible, since whenever branches
 		 * cross, only one is moving directions.
 		 */
-		assert(target * 2 <= i);
+		graph_assert(target * 2 <= i);
 
 		if (target * 2 == i) {
 			/*
 			 * This column is already in the
 			 * correct place
 			 */
-			assert(graph->mapping[i] == -1);
+			graph_assert(graph->mapping[i] == -1);
 			graph->mapping[i] = target;
 		} else if (graph->mapping[i - 1] < 0) {
 			/*
@@ -1225,8 +1227,8 @@ 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.
 			 */
-			assert(graph->mapping[i - 1] > target);
-			assert(graph->mapping[i - 2] < 0);
+			graph_assert(graph->mapping[i - 1] > target);
+			graph_assert(graph->mapping[i - 2] < 0);
 			graph->mapping[i - 2] = target;
 			/*
 			 * Mark this branch as the horizontal edge to
-- 
gitgitgadget

[PATCH 3/3] t4215: add bigger graph collapse test

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

	| | | | | | *   7_M4
	| |_|_|_|_|/|\
	|/| | | | |/ /
	| | | | |/| /
	| | | |/| |/
	| | |/| |/|
	| |/| |/| |
	| | |/| | |
	| | * | | | 7_G

Document this behavior with a test. This behavior is new, as the
behavior in v2.24.1 has the following output:

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

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:

	| | | | | | *   7_M4
	| |_|_|_|_|/|\
	|/| | | | |/ /
	| | |_|_|/| /
	| |/| | | |/
	| | | |_|/|
	| | |/| | |
	| | * | | | 7_G

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

diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index ddf6f6f5d3..be2c24564b 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -282,4 +282,67 @@ test_expect_success 'log --graph with multiple tips' '
 	EOF
 '
 
+test_expect_success '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

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

[Jeff King]

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

Re: [PATCH 2/3] graph: replace assert() with graph_assert() macro

[Jeff King]

On Tue, Jan 07, 2020 at 02:55:46PM +0000, Derrick Stolee via GitGitGadget wrote:

> From: Derrick Stolee <dstolee@microsoft.com>
> 
> The assert() macro is sometimes compiled out. Instead, switch these into
> BUG() statements using our own custom macro.
> 
> Reported-by: Eric Sunshine <sunshine@sunshineco.com>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>

I can buy the argument that compiling with and without NDEBUG can lead
to confusion. But if that is the case, wouldn't it be so for all of the
assert() calls, not just ones in the graph code?

Previous discussions[1] seemed to conclude that having a kernel-style
BUG_ON() is probably the right way forward. I.e., replace this:

> +#define graph_assert(exp) if (!(exp)) { BUG("assert failed: "#exp""); }

with something similar in git-compat-util.h. Even if we don't convert
everybody to it immediately, it would be available for use.

At any rate, I think this patch (and the third one) can be post-v2.25.
But we'd want the first one before the release.

-Peff

[1] https://lore.kernel.org/git/20171122223827.26773-1-sbeller@google.com/

Re: [PATCH 3/3] t4215: add bigger graph collapse test

[Jeff King]

On Tue, Jan 07, 2020 at 02:55:47PM +0000, Derrick Stolee via GitGitGadget wrote:

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

Thanks for constructing this larger case.

As for including this patch, I could take or leave it for now. I like
the idea of documenting things further, but unless it's marked
expect_failure, I don't think it's going to call anybody's attention
more than this thread already has.

So I'd love to hear what James thinks should happen here, given that
it's an extension of his other work. But I'd just as soon punt on the
patch until we decide whether it _should_ change (and then either mark
it with expect_failure, or include the test along with a patch changing
the behavior).

-Peff

Re: [PATCH 2/3] graph: replace assert() with graph_assert() macro

[Eric Sunshine]

On Tue, Jan 7, 2020 at 10:36 AM Jeff King <peff@peff.net> wrote:
> On Tue, Jan 07, 2020 at 02:55:46PM +0000, Derrick Stolee via GitGitGadget wrote:
> > The assert() macro is sometimes compiled out. Instead, switch these into
> > BUG() statements using our own custom macro.
>
> I can buy the argument that compiling with and without NDEBUG can lead
> to confusion. But if that is the case, wouldn't it be so for all of the
> assert() calls, not just ones in the graph code?

This wasn't just a matter of potential confusion. It's one thing to
have assert()s in the code in general, but another thing when a
scripted test specifically depends upon the asserted condition, as was
the case with the test as originally proposed. Since the final patch
series removes that particular assert() altogether, it's perhaps not
that important anymore.

Re: [PATCH 0/3] Fix two bugs in graph.c

[Junio C Hamano]

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

> This is a possible fix for the bug reported in [1].
>
> The first commit fixes the runtime failure due to the assert() statement.
>
> The second commit replaces the assert() statements with a macro that
> triggers a BUG().
>
> The third commit adds another test that shows a more complicated example and
> how the new code in v2.25.0-rc1 has a behavior change that is not
> necessarily wanted.
>
> Thanks, -Stolee

Thanks, all, for so quickly resolving the issue.

Will queue.

>
> [1] 
> https://lore.kernel.org/git/CAHt=fUXTHc4JPsapvHKnw5vHhp2cBOYRNfdaSDWBUnKt8fWfeA@mail.gmail.com/



>
> Derrick Stolee (3):
>   graph: fix case that hit assert()
>   graph: replace assert() with graph_assert() macro
>   t4215: add bigger graph collapse test
>
>  graph.c                      |  39 +++++++------
>  t/t4215-log-skewed-merges.sh | 105 +++++++++++++++++++++++++++++++++++
>  2 files changed, 126 insertions(+), 18 deletions(-)
>
>
> base-commit: 8679ef24ed64018bb62170c43ce73e0261c0600a
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-517%2Fderrickstolee%2Fgraph-assert-fix-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-517/derrickstolee/graph-assert-fix-v1
> Pull-Request: https://github.com/gitgitgadget/git/pull/517

Re: [PATCH 3/3] t4215: add bigger graph collapse test

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Tue, Jan 07, 2020 at 02:55:47PM +0000, Derrick Stolee via GitGitGadget wrote:
>
>> 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.
>
> Thanks for constructing this larger case.
>
> As for including this patch, I could take or leave it for now. I like
> the idea of documenting things further, but unless it's marked
> expect_failure, I don't think it's going to call anybody's attention
> more than this thread already has.
>
> So I'd love to hear what James thinks should happen here, given that
> it's an extension of his other work. But I'd just as soon punt on the
> patch until we decide whether it _should_ change (and then either mark
> it with expect_failure, or include the test along with a patch changing
> the behavior).

... and nobody CC'ed the person from whom they want to hear opinion?

;-)

Re: [PATCH 3/3] t4215: add bigger graph collapse test

[Jeff King]

On Tue, Jan 07, 2020 at 10:02:48AM -0800, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > On Tue, Jan 07, 2020 at 02:55:47PM +0000, Derrick Stolee via GitGitGadget wrote:
> >
> >> 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.
> >
> > Thanks for constructing this larger case.
> >
> > As for including this patch, I could take or leave it for now. I like
> > the idea of documenting things further, but unless it's marked
> > expect_failure, I don't think it's going to call anybody's attention
> > more than this thread already has.
> >
> > So I'd love to hear what James thinks should happen here, given that
> > it's an extension of his other work. But I'd just as soon punt on the
> > patch until we decide whether it _should_ change (and then either mark
> > it with expect_failure, or include the test along with a patch changing
> > the behavior).
> 
> ... and nobody CC'ed the person from whom they want to hear opinion?

Doh, thank you. :) I cc'd him in the earlier thread, but GGG creates a
new one.

-Peff

Re: [PATCH 3/3] t4215: add bigger graph collapse test

[Derrick Stolee]

On 1/7/2020 1:04 PM, Jeff King wrote:
> On Tue, Jan 07, 2020 at 10:02:48AM -0800, Junio C Hamano wrote:
> 
>> Jeff King <peff@peff.net> writes:
>>
>>> On Tue, Jan 07, 2020 at 02:55:47PM +0000, Derrick Stolee via GitGitGadget wrote:
>>>
>>>> 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.
>>>
>>> Thanks for constructing this larger case.
>>>
>>> As for including this patch, I could take or leave it for now. I like
>>> the idea of documenting things further, but unless it's marked
>>> expect_failure, I don't think it's going to call anybody's attention
>>> more than this thread already has.

I think that's fine. I do believe this example demonstrates that the
behavior has changed, so adding an expect_failure (with the correct
expected output) may provide more motivation to fix the issue.

>>> So I'd love to hear what James thinks should happen here, given that
>>> it's an extension of his other work. But I'd just as soon punt on the
>>> patch until we decide whether it _should_ change (and then either mark
>>> it with expect_failure, or include the test along with a patch changing
>>> the behavior).
>>
>> ... and nobody CC'ed the person from whom they want to hear opinion?
> 
> Doh, thank you. :) I cc'd him in the earlier thread, but GGG creates a
> new one.

Sorry, that was my fault. I definitely intended to CC him, but forgot
when going through those who _wrote_ on the previous thread.

-Stolee

Re: [PATCH 2/3] graph: replace assert() with graph_assert() macro

[Derrick Stolee]

On 1/7/2020 10:51 AM, Eric Sunshine wrote:
> On Tue, Jan 7, 2020 at 10:36 AM Jeff King <peff@peff.net> wrote:
>> On Tue, Jan 07, 2020 at 02:55:46PM +0000, Derrick Stolee via GitGitGadget wrote:
>>> The assert() macro is sometimes compiled out. Instead, switch these into
>>> BUG() statements using our own custom macro.
>>
>> I can buy the argument that compiling with and without NDEBUG can lead
>> to confusion. But if that is the case, wouldn't it be so for all of the
>> assert() calls, not just ones in the graph code?
> 
> This wasn't just a matter of potential confusion. It's one thing to
> have assert()s in the code in general, but another thing when a
> scripted test specifically depends upon the asserted condition, as was
> the case with the test as originally proposed. Since the final patch
> series removes that particular assert() altogether, it's perhaps not
> that important anymore.

I'm happy to drop this commit, too. I misunderstood your point.

-Stolee

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

[Derrick Stolee]

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

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

[Junio C Hamano]

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

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

[Jeff King]

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

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

[Junio C Hamano]

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.

[PATCH v2 0/2] Fix two bugs in graph.c

[Derrick Stolee via GitGitGadget]

This is a possible fix for the bug reported in [1].

The first commit fixes the runtime failure due to the assert() statement.

The second commit replaces the assert() statements with a macro that
triggers a BUG().

The third commit adds another test that shows a more complicated example and
how the new code in v2.25.0-rc1 has a behavior change that is not
necessarily wanted.

Thanks, -Stolee

[1] 
https://lore.kernel.org/git/CAHt=fUXTHc4JPsapvHKnw5vHhp2cBOYRNfdaSDWBUnKt8fWfeA@mail.gmail.com/

Derrick Stolee (2):
  graph: fix case that hit assert()
  graph: fix lack of color in horizontal lines

 graph.c                      | 17 +++++----
 t/t4215-log-skewed-merges.sh | 71 ++++++++++++++++++++++++++++++++++++
 2 files changed, 80 insertions(+), 8 deletions(-)


base-commit: 8679ef24ed64018bb62170c43ce73e0261c0600a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-517%2Fderrickstolee%2Fgraph-assert-fix-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-517/derrickstolee/graph-assert-fix-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/517

Range-diff vs v1:

 1:  65186f3ded ! 1:  c05fe2c37a graph: fix case that hit assert()
     @@ -3,17 +3,11 @@
          graph: fix case that hit 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 would fail with the following error:
     +    graph-rendering logic. The code fails an assert() statement when
     +    collapsing multiple edges from a merge.
      
     -            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.
     +    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.
      
     @@ -30,18 +24,45 @@
      
          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
     +    the first line, and 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.
     +    The new behavior in 0f0f389f12 (graph: tidy up display of
     +    left-skewed merges, 2019-10-15) caused the behavior change that
     +    made this assertion failure possible. In addition to making the
     +    assert possible, it also changed how multiple edges collapse.
     +
     +    In a larger example, the current code will output a collapse
     +    as follows:
     +
     +            | | | | | | *
     +            | |_|_|_|_|/|\
     +            |/| | | | |/ /
     +            | | | | |/| /
     +            | | | |/| |/
     +            | | |/| |/|
     +            | |/| |/| |
     +            | | |/| | |
     +            | | * | | |
     +
     +    However, the intended collapse should allow multiple horizontal lines
     +    as follows:
     +
     +            | | | | | | *
     +            | |_|_|_|_|/|\
     +            |/| | | | |/ /
     +            | | |_|_|/| /
     +            | |/| | | |/
     +            | | | |_|/|
     +            | | |/| | |
     +            | | * | | |
     +
     +    This behavior is not corrected by this change, but is noted for a later
     +    update.
      
          Helped-by: Jeff King <peff@peff.net>
          Reported-by: Bradley Smith <brad@brad-smith.co.uk>
     @@ -50,36 +71,6 @@
       diff --git a/graph.c b/graph.c
       --- a/graph.c
       +++ b/graph.c
     -@@
     - 	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
     -@@
     - 			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;
     - 	}
     - 
     - 	/*
      @@
       			 *
       			 * The space just to the left of this
 2:  5dd305d2f0 ! 2:  11887bd38d graph: replace assert() with graph_assert() macro
     @@ -1,100 +1,86 @@
      Author: Derrick Stolee <dstolee@microsoft.com>
      
     -    graph: replace assert() with graph_assert() macro
     +    graph: fix lack of color in horizontal lines
      
     -    The assert() macro is sometimes compiled out. Instead, switch these into
     -    BUG() statements using our own custom macro.
     +    In some cases, horizontal lines in rendered graphs can lose 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.
      
     -    Reported-by: Eric Sunshine <sunshine@sunshineco.com>
     +    Add a test to t4215-log-skewed-merges.sh to prevent regression.
     +
     +    Reported-by: Jeff King <peff@peff.net>
          Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
      
       diff --git a/graph.c b/graph.c
       --- a/graph.c
       +++ b/graph.c
      @@
     - #include "revision.h"
     - #include "argv-array.h"
     - 
     -+#define graph_assert(exp) if (!(exp)) { BUG("assert failed: "#exp""); }
     -+
     - /* Internal API */
     - 
     - /*
     -@@
     - 	struct git_graph *graph = data;
     - 	static struct strbuf msgbuf = STRBUF_INIT;
     - 
     --	assert(opt);
     -+	graph_assert(opt);
     - 
     - 	strbuf_reset(&msgbuf);
     - 	if (opt->line_prefix)
     -@@
     - 	 *
     - 	 * We need 2 extra rows for every parent over 2.
     - 	 */
     --	assert(graph->num_parents >= 3);
     -+	graph_assert(graph->num_parents >= 3);
     + 	int i, j;
       
     - 	/*
     - 	 * graph->expansion_row tracks the current expansion row we are on.
     - 	 * It should be in the range [0, num_expansion_rows - 1]
     - 	 */
     --	assert(0 <= graph->expansion_row &&
     -+	graph_assert(0 <= graph->expansion_row &&
     - 	       graph->expansion_row < graph_num_expansion_rows(graph));
     + 	struct commit_list *first_parent = first_interesting_parent(graph);
     +-	int seen_parent = 0;
     ++	struct column *parent_col = NULL;
       
       	/*
     + 	 * Output the post-merge row
      @@
     - 	 * (We should only see boundary commits when revs->boundary is set.)
     - 	 */
     - 	if (graph->commit->object.flags & BOUNDARY) {
     --		assert(graph->revs->boundary);
     -+		graph_assert(graph->revs->boundary);
     - 		graph_line_addch(line, 'o');
     - 		return;
     + 			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;
       	}
       
       	/*
     --	 * get_revision_mark() handles all other cases without assert()
     -+	 * get_revision_mark() handles all other cases without graph_assert()
     - 	 */
     - 	graph_line_addstr(line, get_revision_mark(graph->revs, graph->commit));
     - }
     -@@
     - 
     - 			for (j = 0; j < graph->num_parents; j++) {
     - 				par_column = graph_find_new_column_by_commit(graph, parents->item);
     --				assert(par_column >= 0);
     -+				graph_assert(par_column >= 0);
     - 
     - 				c = merge_chars[idx];
     - 				graph_line_write_column(line, &graph->new_columns[par_column], c);
     +
     + diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
     + --- a/t/t4215-log-skewed-merges.sh
     + +++ b/t/t4215-log-skewed-merges.sh
      @@
     - 		 * the graph much more legible, since whenever branches
     - 		 * cross, only one is moving directions.
     - 		 */
     --		assert(target * 2 <= i);
     -+		graph_assert(target * 2 <= i);
     + 	EOF
     + '
       
     - 		if (target * 2 == i) {
     - 			/*
     - 			 * This column is already in the
     - 			 * correct place
     - 			 */
     --			assert(graph->mapping[i] == -1);
     -+			graph_assert(graph->mapping[i] == -1);
     - 			graph->mapping[i] = target;
     - 		} else if (graph->mapping[i - 1] < 0) {
     - 			/*
     -@@
     - 			 * The space just to the left of this
     - 			 * branch should always be empty.
     - 			 */
     --			assert(graph->mapping[i - 1] > target);
     --			assert(graph->mapping[i - 2] < 0);
     -+			graph_assert(graph->mapping[i - 1] > target);
     -+			graph_assert(graph->mapping[i - 2] < 0);
     - 			graph->mapping[i - 2] = target;
     - 			/*
     - 			 * Mark this branch as the horizontal edge to
     ++test_expect_success 'log --graph with multiple tips and colors' '
     ++	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
     ++	cat >expect.colors <<-\EOF &&
     ++	*   6_I
     ++	<RED>|<RESET><GREEN>\<RESET>
     ++	<RED>|<RESET> <GREEN>|<RESET> *   6_H
     ++	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET><BLUE>\<RESET>
     ++	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET> * 6_G
     ++	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET> <BLUE>|<RESET> * 6_F
     ++	<RED>|<RESET> <GREEN>|<RESET><RED>_<RESET><YELLOW>|<RESET><RED>_<RESET><BLUE>|<RESET><RED>/<RESET><GREEN>|<RESET>
     ++	<RED>|<RESET><RED>/<RESET><GREEN>|<RESET> <YELLOW>|<RESET> <BLUE>|<RESET><GREEN>/<RESET>
     ++	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET><GREEN>/<RESET><BLUE>|<RESET>
     ++	<RED>|<RESET> <GREEN>|<RESET><GREEN>/<RESET><YELLOW>|<RESET> <BLUE>|<RESET>
     ++	<RED>|<RESET> <GREEN>|<RESET> * <BLUE>|<RESET> 6_E
     ++	<RED>|<RESET> * <CYAN>|<RESET> <BLUE>|<RESET> 6_D
     ++	<RED>|<RESET> <BLUE>|<RESET> <CYAN>|<RESET><BLUE>/<RESET>
     ++	<RED>|<RESET> <BLUE>|<RESET><BLUE>/<RESET><CYAN>|<RESET>
     ++	* <BLUE>|<RESET> <CYAN>|<RESET> 6_C
     ++	<CYAN>|<RESET> <BLUE>|<RESET><CYAN>/<RESET>
     ++	<CYAN>|<RESET><CYAN>/<RESET><BLUE>|<RESET>
     ++	* <BLUE>|<RESET> 6_B
     ++	<BLUE>|<RESET><BLUE>/<RESET>
     ++	* 6_A
     ++	EOF
     ++	git log --color=always --graph --date-order --pretty=tformat:%s 6_1 6_3 6_5 >actual.colors.raw &&
     ++	test_decode_color <actual.colors.raw | sed "s/ *\$//" >actual.colors &&
     ++	test_cmp expect.colors actual.colors
     ++'
     ++
     + test_done
 3:  f74e82bea6 < -:  ---------- t4215: add bigger graph collapse test

-- 
gitgitgadget

[PATCH v2 1/2] graph: fix case that hit assert()

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

A failure was reported in "git log --graph --all" with the new
graph-rendering logic. The code fails an assert() statement when
collapsing multiple edges from a merge.

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

The new behavior in 0f0f389f12 (graph: tidy up display of
left-skewed merges, 2019-10-15) caused the behavior change that
made this assertion failure possible. In addition to making the
assert possible, it also changed how multiple edges collapse.

In a larger example, the current code will output a collapse
as follows:

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

However, the intended collapse should allow multiple horizontal lines
as follows:

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

This behavior is not corrected by this change, but is noted for a later
update.

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                      |  4 ----
 t/t4215-log-skewed-merges.sh | 42 ++++++++++++++++++++++++++++++++++++
 2 files changed, 42 insertions(+), 4 deletions(-)

diff --git a/graph.c b/graph.c
index 66ae18add8..f514ed3efa 100644
--- a/graph.c
+++ b/graph.c
@@ -1219,13 +1219,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
-- 
gitgitgadget

[PATCH v2 2/2] graph: fix lack of color in horizontal lines

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

In some cases, horizontal lines in rendered graphs can lose 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.

Add a test to t4215-log-skewed-merges.sh to prevent regression.

Reported-by: Jeff King <peff@peff.net>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 graph.c                      | 13 +++++++++----
 t/t4215-log-skewed-merges.sh | 29 +++++++++++++++++++++++++++++
 2 files changed, 38 insertions(+), 4 deletions(-)

diff --git a/graph.c b/graph.c
index f514ed3efa..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;
 	}
 
 	/*
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index ddf6f6f5d3..5661ed5881 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -282,4 +282,33 @@ test_expect_success 'log --graph with multiple tips' '
 	EOF
 '
 
+test_expect_success 'log --graph with multiple tips and colors' '
+	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
+	cat >expect.colors <<-\EOF &&
+	*   6_I
+	<RED>|<RESET><GREEN>\<RESET>
+	<RED>|<RESET> <GREEN>|<RESET> *   6_H
+	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET><BLUE>\<RESET>
+	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET> * 6_G
+	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET> <BLUE>|<RESET> * 6_F
+	<RED>|<RESET> <GREEN>|<RESET><RED>_<RESET><YELLOW>|<RESET><RED>_<RESET><BLUE>|<RESET><RED>/<RESET><GREEN>|<RESET>
+	<RED>|<RESET><RED>/<RESET><GREEN>|<RESET> <YELLOW>|<RESET> <BLUE>|<RESET><GREEN>/<RESET>
+	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET><GREEN>/<RESET><BLUE>|<RESET>
+	<RED>|<RESET> <GREEN>|<RESET><GREEN>/<RESET><YELLOW>|<RESET> <BLUE>|<RESET>
+	<RED>|<RESET> <GREEN>|<RESET> * <BLUE>|<RESET> 6_E
+	<RED>|<RESET> * <CYAN>|<RESET> <BLUE>|<RESET> 6_D
+	<RED>|<RESET> <BLUE>|<RESET> <CYAN>|<RESET><BLUE>/<RESET>
+	<RED>|<RESET> <BLUE>|<RESET><BLUE>/<RESET><CYAN>|<RESET>
+	* <BLUE>|<RESET> <CYAN>|<RESET> 6_C
+	<CYAN>|<RESET> <BLUE>|<RESET><CYAN>/<RESET>
+	<CYAN>|<RESET><CYAN>/<RESET><BLUE>|<RESET>
+	* <BLUE>|<RESET> 6_B
+	<BLUE>|<RESET><BLUE>/<RESET>
+	* 6_A
+	EOF
+	git log --color=always --graph --date-order --pretty=tformat:%s 6_1 6_3 6_5 >actual.colors.raw &&
+	test_decode_color <actual.colors.raw | sed "s/ *\$//" >actual.colors &&
+	test_cmp expect.colors actual.colors
+'
+
 test_done
-- 
gitgitgadget

Re: [PATCH v2 1/2] graph: fix case that hit assert()

[Junio C Hamano]

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

> From: Derrick Stolee <dstolee@microsoft.com>
> Subject: Re: [PATCH v2 1/2] graph: fix case that hit assert()
>
> A failure was reported in "git log --graph --all" with the new
> graph-rendering logic. The code fails an assert() statement when
> collapsing multiple edges from a merge.
>
> 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:
>
>     | | | | *
>     | |_|_|/|
>     |/| | |/
>     | | |/|
>     | |/| |
>     | * | |
>     * | | |

I was sort-of expecting to see

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

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

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

    we trigger an assert():

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

    The assert was introduced by eaf158f8 ("graph API: Use horizontal
    lines for more compact graphs", 2009-04-21), which is quite old.
    ...

near the beginning of this commit, though.

> In a larger example, the current code will output a collapse
> as follows:
>
> 	| | | | | | *
> 	| |_|_|_|_|/|\
> 	|/| | | | |/ /
> 	| | | | |/| /
> 	| | | |/| |/
> 	| | |/| |/|
> 	| |/| |/| |
> 	| | |/| | |
> 	| | * | | |
>
> However, the intended collapse should allow multiple horizontal lines
> as follows:
>
> 	| | | | | | *
> 	| |_|_|_|_|/|\
> 	|/| | | | |/ /
> 	| | |_|_|/| /
> 	| |/| | | |/
> 	| | | |_|/|
> 	| | |/| | |
> 	| | * | | |
>
> This behavior is not corrected by this change, but is noted for a later
> update.

This part is new and looks like a good thing to mention.

Re: [PATCH v2 2/2] graph: fix lack of color in horizontal lines

[Junio C Hamano]

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

> From: Derrick Stolee <dstolee@microsoft.com>
>
> In some cases, horizontal lines in rendered graphs can lose 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.
>
> Add a test to t4215-log-skewed-merges.sh to prevent regression.
>
> Reported-by: Jeff King <peff@peff.net>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---

Thanks.  Looks good.

Re: [PATCH v2 1/2] graph: fix case that hit assert()

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
>
>> From: Derrick Stolee <dstolee@microsoft.com>
>> Subject: Re: [PATCH v2 1/2] graph: fix case that hit assert()
>>
>> A failure was reported in "git log --graph --all" with the new
>> graph-rendering logic. The code fails an assert() statement when
>> collapsing multiple edges from a merge.
>>
>> 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:
>>
>>     | | | | *
>>     | |_|_|/|
>>     |/| | |/
>>     | | |/|
>>     | |/| |
>>     | * | |
>>     * | | |
>
> I was sort-of expecting to see
> ...
> near the beginning of this commit, though.

Will do this locally before using them in rc2.

Thanks.

Re: [PATCH v2 1/2] graph: fix case that hit assert()

[Derrick Stolee]

On 1/8/2020 12:34 PM, Junio C Hamano wrote:
> Junio C Hamano <gitster@pobox.com> writes:
> 
>> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
>>
>>> From: Derrick Stolee <dstolee@microsoft.com>
>>> Subject: Re: [PATCH v2 1/2] graph: fix case that hit assert()
>>>
>>> A failure was reported in "git log --graph --all" with the new
>>> graph-rendering logic. The code fails an assert() statement when
>>> collapsing multiple edges from a merge.
>>>
>>> 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:
>>>
>>>     | | | | *
>>>     | |_|_|/|
>>>     |/| | |/
>>>     | | |/|
>>>     | |/| |
>>>     | * | |
>>>     * | | |
>>
>> I was sort-of expecting to see
>> ...
>> near the beginning of this commit, though.
> 
> Will do this locally before using them in rc2.

Sounds good to me. Sorry for the delay in doing it myself.

-Stolee