[07/11] graph: commit and post-merge lines for left-skewed merges
diff mbox series

Message ID 6c173663aac37f1d314db8637cf4a243066b8078.1570724021.git.gitgitgadget@gmail.com
State New
Headers show
Series
  • Improve the readability of log --graph output
Related show

Commit Message

Utsav Shah via GitGitGadget Oct. 10, 2019, 4:13 p.m. UTC
From: James Coglan <jcoglan@gmail.com>

Following the introduction of "left-skewed" merges, which are merges
whose first parent fuses with another edge to its left, we have some
more edge cases to deal with in the display of commit and post-merge
lines.

The current graph code handles the following cases for edges appearing
to the right of the commit (*) on commit lines. A 2-way merge is usually
followed by vertical lines:

        | | |
        | * |
        | |\ \

An octopus merge (more than two parents) is always followed by edges
sloping to the right:

        | |  \          | |    \
        | *-. \         | *---. \
        | |\ \ \        | |\ \ \ \

A 2-way merge is followed by a right-sloping edge if the commit line
immediately follows a post-merge line for a commit that appears in the
same column as the current commit, or any column to the left of that:

        | *             | * |
        | |\            | |\ \
        | * \           | | * \
        | |\ \          | | |\ \

This commit introduces the following new cases for commit lines. If a
2-way merge skews to the left, then the edges to its right are always
vertical lines, even if the commit follows a post-merge line:

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

A commit with 3 parents that skews left is followed by vertical edges:

        | | |
        | * |
        |/|\ \

If a 3-way left-skewed merge commit appears immediately after a
post-merge line, then it may be followed the right-sloping edges, just
like a 2-way merge that is not skewed.

        | |\
        | * \
        |/|\ \

Octopus merges with 4 or more parents that skew to the left will always
be followed by right-sloping edges, because the existing columns need to
expand around the merge.

        | |  \
        | *-. \
        |/|\ \ \

On post-merge lines, usually all edges following the current commit
slope to the right:

        | * | |
        | |\ \ \

However, if the commit is a left-skewed 2-way merge, the edges to its
right remain vertical. We also need to display a space after the
vertical line descending from the commit marker, whereas this line would
normally be followed by a backslash.

        | * | |
        |/| | |

If a left-skewed merge has more than 2 parents, then the edges to its
right are still sloped as they bend around the edges introduced by the
merge.

        | * | |
        |/|\ \ \

To handle these new cases, we need to know not just how many parents
each commit has, but how many new columns it adds to the display; this
quantity is recorded in the `edges_added` field for the current commit,
and `prev_edges_added` field for the previous commit.

Here, "column" refers to visual columns, not the logical columns of the
`columns` array. This is because even if all the commit's parents end up
fusing with existing edges, they initially introduce distinct edges in
the commit and post-merge lines before those edges collapse. For
example, a 3-way merge whose 2nd and 3rd parents fuse with existing
edges still introduces 2 visual columns that affect the display of edges
to their right.

        | | |  \
        | | *-. \
        | | |\ \ \
        | |_|/ / /
        |/| | / /
        | | |/ /
        | |/| |
        | | | |

This merge does not introduce any *logical* columns; there are 4 edges
before and after this commit once all edges have collapsed. But it does
initially introduce 2 new edges that need to be accommodated by the
edges to their right.

Signed-off-by: James Coglan <jcoglan@gmail.com>
---
 graph.c                      |  63 +++++++++++++--
 t/t4215-log-skewed-merges.sh | 151 +++++++++++++++++++++++++++++++++++
 2 files changed, 209 insertions(+), 5 deletions(-)

Comments

Derrick Stolee Oct. 10, 2019, 5:49 p.m. UTC | #1
On 10/10/2019 12:13 PM, James Coglan via GitGitGadget wrote:
> From: James Coglan <jcoglan@gmail.com>
> 
> Following the introduction of "left-skewed" merges, which are merges
> whose first parent fuses with another edge to its left, we have some
> more edge cases to deal with in the display of commit and post-merge
> lines.
> 
> The current graph code handles the following cases for edges appearing
> to the right of the commit (*) on commit lines. A 2-way merge is usually
> followed by vertical lines:
> 
>         | | |
>         | * |
>         | |\ \
> 
> An octopus merge (more than two parents) is always followed by edges
> sloping to the right:
> 
>         | |  \          | |    \
>         | *-. \         | *---. \
>         | |\ \ \        | |\ \ \ \
> 
> A 2-way merge is followed by a right-sloping edge if the commit line
> immediately follows a post-merge line for a commit that appears in the
> same column as the current commit, or any column to the left of that:
> 
>         | *             | * |
>         | |\            | |\ \
>         | * \           | | * \
>         | |\ \          | | |\ \
> 
> This commit introduces the following new cases for commit lines. If a
> 2-way merge skews to the left, then the edges to its right are always
> vertical lines, even if the commit follows a post-merge line:
> 
>         | | |           | |\
>         | * |           | * |
>         |/| |           |/| |
> 
> A commit with 3 parents that skews left is followed by vertical edges:
> 
>         | | |
>         | * |
>         |/|\ \
> 
> If a 3-way left-skewed merge commit appears immediately after a
> post-merge line, then it may be followed the right-sloping edges, just
> like a 2-way merge that is not skewed.
> 
>         | |\
>         | * \
>         |/|\ \
> 
> Octopus merges with 4 or more parents that skew to the left will always
> be followed by right-sloping edges, because the existing columns need to
> expand around the merge.
> 
>         | |  \
>         | *-. \
>         |/|\ \ \
> 
> On post-merge lines, usually all edges following the current commit
> slope to the right:
> 
>         | * | |
>         | |\ \ \
> 
> However, if the commit is a left-skewed 2-way merge, the edges to its
> right remain vertical. We also need to display a space after the
> vertical line descending from the commit marker, whereas this line would
> normally be followed by a backslash.
> 
>         | * | |
>         |/| | |
> 
> If a left-skewed merge has more than 2 parents, then the edges to its
> right are still sloped as they bend around the edges introduced by the
> merge.
> 
>         | * | |
>         |/|\ \ \
> 
> To handle these new cases, we need to know not just how many parents
> each commit has, but how many new columns it adds to the display; this
> quantity is recorded in the `edges_added` field for the current commit,
> and `prev_edges_added` field for the previous commit.
> 
> Here, "column" refers to visual columns, not the logical columns of the
> `columns` array. This is because even if all the commit's parents end up
> fusing with existing edges, they initially introduce distinct edges in
> the commit and post-merge lines before those edges collapse. For
> example, a 3-way merge whose 2nd and 3rd parents fuse with existing
> edges still introduces 2 visual columns that affect the display of edges
> to their right.
> 
>         | | |  \
>         | | *-. \
>         | | |\ \ \
>         | |_|/ / /
>         |/| | / /
>         | | |/ /
>         | |/| |
>         | | | |
> 
> This merge does not introduce any *logical* columns; there are 4 edges
> before and after this commit once all edges have collapsed. But it does
> initially introduce 2 new edges that need to be accommodated by the
> edges to their right.
> 
> Signed-off-by: James Coglan <jcoglan@gmail.com>
> ---
>  graph.c                      |  63 +++++++++++++--
>  t/t4215-log-skewed-merges.sh | 151 +++++++++++++++++++++++++++++++++++
>  2 files changed, 209 insertions(+), 5 deletions(-)
> 
> diff --git a/graph.c b/graph.c
> index 9136173e03..fb2e42850f 100644
> --- a/graph.c
> +++ b/graph.c
> @@ -197,6 +197,46 @@ struct git_graph {
>  	 * 		|/| | | | |		| | | | | *
>  	 */
>  	int merge_layout;
> +	/*
> +	 * The number of columns added to the graph by the current commit. For
> +	 * 2-way and octopus merges, this is is usually one less than the
> +	 * number of parents:
> +	 *
> +	 * 		| | |			| |    \
> +	 *		| * |			| *---. \
> +	 *		| |\ \			| |\ \ \ \
> +	 *		| | | |         	| | | | | |
> +	 *
> +	 *		num_parents: 2		num_parents: 4
> +	 *		edges_added: 1		edges_added: 3
> +	 *
> +	 * For left-skewed merges, the first parent fuses with its neighbor and
> +	 * so one less column is added:
> +	 *
> +	 *		| | |			| |  \
> +	 *		| * |			| *-. \
> +	 *		|/| |			|/|\ \ \
> +	 *		| | |			| | | | |
> +	 *
> +	 *		num_parents: 2		num_parents: 4
> +	 *		edges_added: 0		edges_added: 2
> +	 *
> +	 * This number determines how edges to the right of the merge are
> +	 * displayed in commit and post-merge lines; if no columns have been
> +	 * added then a vertical line should be used where a right-tracking
> +	 * line would otherwise be used.
> +	 *
> +	 *		| * \			| * |
> +	 *		| |\ \			|/| |
> +	 *		| | * \			| * |
> +	 */
> +	int edges_added;
> +	/*
> +	 * The number of columns added by the previous commit, which is used to
> +	 * smooth edges appearing to the right of a commit in a commit line
> +	 * following a post-merge line.
> +	 */
> +	int prev_edges_added;
>  	/*
>  	 * The maximum number of columns that can be stored in the columns
>  	 * and new_columns arrays.  This is also half the number of entries
> @@ -309,6 +349,8 @@ struct git_graph *graph_init(struct rev_info *opt)
>  	graph->commit_index = 0;
>  	graph->prev_commit_index = 0;
>  	graph->merge_layout = 0;
> +	graph->edges_added = 0;
> +	graph->prev_edges_added = 0;
>  	graph->num_columns = 0;
>  	graph->num_new_columns = 0;
>  	graph->mapping_size = 0;
> @@ -670,6 +712,9 @@ void graph_update(struct git_graph *graph, struct commit *commit)
>  	 */
>  	graph_update_columns(graph);
>  
> +	graph->prev_edges_added = graph->edges_added;
> +	graph->edges_added = graph->num_parents + graph->merge_layout - 2;
> +
>  	graph->expansion_row = 0;
>  
>  	/*
> @@ -943,12 +988,13 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  
>  			if (graph->num_parents > 2)
>  				graph_draw_octopus_merge(graph, sb);
> -		} else if (seen_this && (graph->num_parents > 2)) {
> +		} else if (seen_this && (graph->edges_added > 1)) {
>  			strbuf_write_column(sb, col, '\\');
> -		} else if (seen_this && (graph->num_parents == 2)) {
> +		} else if (seen_this && (graph->edges_added == 1)) {
>  			/*
> -			 * This is a 2-way merge commit.
> -			 * There is no GRAPH_PRE_COMMIT stage for 2-way
> +			 * This is either a right-skewed 2-way merge
> +			 * commit, or a left-skewed 3-way merge.
> +			 * There is no GRAPH_PRE_COMMIT stage for such
>  			 * merges, so this is the first line of output
>  			 * for this commit.  Check to see what the previous
>  			 * line of output was.
> @@ -960,6 +1006,7 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  			 * makes the output look nicer.
>  			 */
>  			if (graph->prev_state == GRAPH_POST_MERGE &&
> +			    graph->prev_edges_added > 0 &&
>  			    graph->prev_commit_index < i)
>  				strbuf_write_column(sb, col, '\\');
>  			else
> @@ -1031,8 +1078,14 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
>  				else
>  					idx++;
>  			}
> +			if (graph->edges_added == 0)
> +				strbuf_addch(sb, ' ');
> +
>  		} else if (seen_this) {
> -			strbuf_write_column(sb, col, '\\');
> +			if (graph->edges_added > 0)
> +				strbuf_write_column(sb, col, '\\');
> +			else
> +				strbuf_write_column(sb, col, '|');
>  			strbuf_addch(sb, ' ');
>  		} else {
>  			strbuf_write_column(sb, col, '|');
> diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
> index cfaba40f97..e479d6e676 100755
> --- a/t/t4215-log-skewed-merges.sh
> +++ b/t/t4215-log-skewed-merges.sh
> @@ -39,4 +39,155 @@ test_expect_success 'log --graph with left-skewed merge' '
>  	test_cmp expect actual
>  '
>  
> +test_expect_success 'setup nested left-skewed merge' '
> +	git checkout --orphan 1_p &&
> +	test_commit 1_A &&
> +	test_commit 1_B &&
> +	test_commit 1_C &&
> +	git checkout -b 1_q @^ && test_commit 1_D &&
> +	git checkout 1_p && git merge --no-ff 1_q -m 1_E &&
> +	git checkout -b 1_r @~3 && test_commit 1_F &&
> +	git checkout 1_p && git merge --no-ff 1_r -m 1_G &&
> +	git checkout @^^ && git merge --no-ff 1_p -m 1_H
> +'
> +
> +cat > expect <<\EOF
> +*   1_H
> +|\
> +| *   1_G
> +| |\
> +| | * 1_F
> +| * | 1_E
> +|/| |
> +| * | 1_D
> +* | | 1_C
> +|/ /
> +* | 1_B
> +|/
> +* 1_A
> +EOF
> +
> +test_expect_success 'log --graph with nested left-skewed merge' '
> +	git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual &&
> +	test_cmp expect actual
> +'

I should have noticed in your earlier commits, but why don't you keep
the output inside the test suite? You can start with "cat >expect <<-EOF"
to have it ignore leading whitespace. Sorry if there's something else about
this that is causing issues.

> +
> +test_expect_success 'setup nested left-skewed merge following normal merge' '
> +	git checkout --orphan 2_p &&
> +	test_commit 2_A &&
> +	test_commit 2_B &&
> +	test_commit 2_C &&
> +	git checkout -b 2_q @^^ &&
> +	test_commit 2_D &&
> +	test_commit 2_E &&
> +	git checkout -b 2_r @^ && test_commit 2_F &&
> +	git checkout 2_q &&
> +	git merge --no-ff 2_r -m 2_G &&
> +	git merge --no-ff 2_p^ -m 2_H &&
> +	git checkout -b 2_s @^^ && git merge --no-ff 2_q -m 2_J &&
> +	git checkout 2_p && git merge --no-ff 2_s -m 2_K
> +'
> +
> +cat > expect <<\EOF
> +*   2_K
> +|\
> +| *   2_J
> +| |\
> +| | *   2_H
> +| | |\
> +| | * | 2_G
> +| |/| |
> +| | * | 2_F
> +| * | | 2_E
> +| |/ /
> +| * | 2_D
> +* | | 2_C
> +| |/
> +|/|
> +* | 2_B
> +|/
> +* 2_A
> +EOF
> +
> +test_expect_success 'log --graph with nested left-skewed merge following normal merge' '
> +	git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual &&
> +	test_cmp expect actual
> +'
> +
> +test_expect_success 'setup nested right-skewed merge following left-skewed merge' '
> +	git checkout --orphan 3_p &&
> +	test_commit 3_A &&
> +	git checkout -b 3_q &&
> +	test_commit 3_B &&
> +	test_commit 3_C &&
> +	git checkout -b 3_r @^ &&
> +	test_commit 3_D &&
> +	git checkout 3_q && git merge --no-ff 3_r -m 3_E &&
> +	git checkout 3_p && git merge --no-ff 3_q -m 3_F &&
> +	git checkout 3_r && test_commit 3_G &&
> +	git checkout 3_p && git merge --no-ff 3_r -m 3_H &&
> +	git checkout @^^ && git merge --no-ff 3_p -m 3_J
> +'
> +
> +cat > expect <<\EOF
> +*   3_J
> +|\
> +| *   3_H
> +| |\
> +| | * 3_G
> +| * | 3_F
> +|/| |
> +| * |   3_E
> +| |\ \
> +| | |/
> +| | * 3_D
> +| * | 3_C
> +| |/
> +| * 3_B
> +|/
> +* 3_A
> +EOF
> +
> +test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge' '
> +	git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual &&
> +	test_cmp expect actual
> +'
> +
> +test_expect_success 'setup right-skewed merge following a left-skewed one' '
> +	git checkout --orphan 4_p &&
> +	test_commit 4_A &&
> +	test_commit 4_B &&
> +	test_commit 4_C &&
> +	git checkout -b 4_q @^^ && test_commit 4_D &&
> +	git checkout -b 4_r 4_p^ && git merge --no-ff 4_q -m 4_E &&
> +	git checkout -b 4_s 4_p^^ &&
> +	git merge --no-ff 4_r -m 4_F &&
> +	git merge --no-ff 4_p -m 4_G &&
> +	git checkout @^^ && git merge --no-ff 4_s -m 4_H
> +'
> +
> +cat > expect <<\EOF
> +*   4_H
> +|\
> +| *   4_G
> +| |\
> +| * | 4_F
> +|/| |
> +| * |   4_E
> +| |\ \
> +| | * | 4_D
> +| |/ /
> +|/| |
> +| | * 4_C
> +| |/
> +| * 4_B
> +|/
> +* 4_A
> +EOF
> +
> +test_expect_success 'log --graph with right-skewed merge following a left-skewed one' '
> +	git log --graph --date-order --pretty=tformat:%s | sed "s/ *$//" > actual &&
> +	test_cmp expect actual
> +'
> +
>  test_done
>
James Coglan Oct. 11, 2019, 5:04 p.m. UTC | #2
On 10/10/2019 18:49, Derrick Stolee wrote:
> On 10/10/2019 12:13 PM, James Coglan via GitGitGadget wrote:
>> From: James Coglan <jcoglan@gmail.com>
>>
>> Following the introduction of "left-skewed" merges, which are merges
>> whose first parent fuses with another edge to its left, we have some
>> more edge cases to deal with in the display of commit and post-merge
>> lines.
>>
>> The current graph code handles the following cases for edges appearing
>> to the right of the commit (*) on commit lines. A 2-way merge is usually
>> followed by vertical lines:
>>
>>         | | |
>>         | * |
>>         | |\ \
>>
>> An octopus merge (more than two parents) is always followed by edges
>> sloping to the right:
>>
>>         | |  \          | |    \
>>         | *-. \         | *---. \
>>         | |\ \ \        | |\ \ \ \
>>
>> A 2-way merge is followed by a right-sloping edge if the commit line
>> immediately follows a post-merge line for a commit that appears in the
>> same column as the current commit, or any column to the left of that:
>>
>>         | *             | * |
>>         | |\            | |\ \
>>         | * \           | | * \
>>         | |\ \          | | |\ \
>>
>> This commit introduces the following new cases for commit lines. If a
>> 2-way merge skews to the left, then the edges to its right are always
>> vertical lines, even if the commit follows a post-merge line:
>>
>>         | | |           | |\
>>         | * |           | * |
>>         |/| |           |/| |
>>
>> A commit with 3 parents that skews left is followed by vertical edges:
>>
>>         | | |
>>         | * |
>>         |/|\ \
>>
>> If a 3-way left-skewed merge commit appears immediately after a
>> post-merge line, then it may be followed the right-sloping edges, just
>> like a 2-way merge that is not skewed.
>>
>>         | |\
>>         | * \
>>         |/|\ \
>>
>> Octopus merges with 4 or more parents that skew to the left will always
>> be followed by right-sloping edges, because the existing columns need to
>> expand around the merge.
>>
>>         | |  \
>>         | *-. \
>>         |/|\ \ \
>>
>> On post-merge lines, usually all edges following the current commit
>> slope to the right:
>>
>>         | * | |
>>         | |\ \ \
>>
>> However, if the commit is a left-skewed 2-way merge, the edges to its
>> right remain vertical. We also need to display a space after the
>> vertical line descending from the commit marker, whereas this line would
>> normally be followed by a backslash.
>>
>>         | * | |
>>         |/| | |
>>
>> If a left-skewed merge has more than 2 parents, then the edges to its
>> right are still sloped as they bend around the edges introduced by the
>> merge.
>>
>>         | * | |
>>         |/|\ \ \
>>
>> To handle these new cases, we need to know not just how many parents
>> each commit has, but how many new columns it adds to the display; this
>> quantity is recorded in the `edges_added` field for the current commit,
>> and `prev_edges_added` field for the previous commit.
>>
>> Here, "column" refers to visual columns, not the logical columns of the
>> `columns` array. This is because even if all the commit's parents end up
>> fusing with existing edges, they initially introduce distinct edges in
>> the commit and post-merge lines before those edges collapse. For
>> example, a 3-way merge whose 2nd and 3rd parents fuse with existing
>> edges still introduces 2 visual columns that affect the display of edges
>> to their right.
>>
>>         | | |  \
>>         | | *-. \
>>         | | |\ \ \
>>         | |_|/ / /
>>         |/| | / /
>>         | | |/ /
>>         | |/| |
>>         | | | |
>>
>> This merge does not introduce any *logical* columns; there are 4 edges
>> before and after this commit once all edges have collapsed. But it does
>> initially introduce 2 new edges that need to be accommodated by the
>> edges to their right.
>>
>> Signed-off-by: James Coglan <jcoglan@gmail.com>
>> ---
>>  graph.c                      |  63 +++++++++++++--
>>  t/t4215-log-skewed-merges.sh | 151 +++++++++++++++++++++++++++++++++++
>>  2 files changed, 209 insertions(+), 5 deletions(-)
>>
>> diff --git a/graph.c b/graph.c
>> index 9136173e03..fb2e42850f 100644
>> --- a/graph.c
>> +++ b/graph.c
>> @@ -197,6 +197,46 @@ struct git_graph {
>>  	 * 		|/| | | | |		| | | | | *
>>  	 */
>>  	int merge_layout;
>> +	/*
>> +	 * The number of columns added to the graph by the current commit. For
>> +	 * 2-way and octopus merges, this is is usually one less than the
>> +	 * number of parents:
>> +	 *
>> +	 * 		| | |			| |    \
>> +	 *		| * |			| *---. \
>> +	 *		| |\ \			| |\ \ \ \
>> +	 *		| | | |         	| | | | | |
>> +	 *
>> +	 *		num_parents: 2		num_parents: 4
>> +	 *		edges_added: 1		edges_added: 3
>> +	 *
>> +	 * For left-skewed merges, the first parent fuses with its neighbor and
>> +	 * so one less column is added:
>> +	 *
>> +	 *		| | |			| |  \
>> +	 *		| * |			| *-. \
>> +	 *		|/| |			|/|\ \ \
>> +	 *		| | |			| | | | |
>> +	 *
>> +	 *		num_parents: 2		num_parents: 4
>> +	 *		edges_added: 0		edges_added: 2
>> +	 *
>> +	 * This number determines how edges to the right of the merge are
>> +	 * displayed in commit and post-merge lines; if no columns have been
>> +	 * added then a vertical line should be used where a right-tracking
>> +	 * line would otherwise be used.
>> +	 *
>> +	 *		| * \			| * |
>> +	 *		| |\ \			|/| |
>> +	 *		| | * \			| * |
>> +	 */
>> +	int edges_added;
>> +	/*
>> +	 * The number of columns added by the previous commit, which is used to
>> +	 * smooth edges appearing to the right of a commit in a commit line
>> +	 * following a post-merge line.
>> +	 */
>> +	int prev_edges_added;
>>  	/*
>>  	 * The maximum number of columns that can be stored in the columns
>>  	 * and new_columns arrays.  This is also half the number of entries
>> @@ -309,6 +349,8 @@ struct git_graph *graph_init(struct rev_info *opt)
>>  	graph->commit_index = 0;
>>  	graph->prev_commit_index = 0;
>>  	graph->merge_layout = 0;
>> +	graph->edges_added = 0;
>> +	graph->prev_edges_added = 0;
>>  	graph->num_columns = 0;
>>  	graph->num_new_columns = 0;
>>  	graph->mapping_size = 0;
>> @@ -670,6 +712,9 @@ void graph_update(struct git_graph *graph, struct commit *commit)
>>  	 */
>>  	graph_update_columns(graph);
>>  
>> +	graph->prev_edges_added = graph->edges_added;
>> +	graph->edges_added = graph->num_parents + graph->merge_layout - 2;
>> +
>>  	graph->expansion_row = 0;
>>  
>>  	/*
>> @@ -943,12 +988,13 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>>  
>>  			if (graph->num_parents > 2)
>>  				graph_draw_octopus_merge(graph, sb);
>> -		} else if (seen_this && (graph->num_parents > 2)) {
>> +		} else if (seen_this && (graph->edges_added > 1)) {
>>  			strbuf_write_column(sb, col, '\\');
>> -		} else if (seen_this && (graph->num_parents == 2)) {
>> +		} else if (seen_this && (graph->edges_added == 1)) {
>>  			/*
>> -			 * This is a 2-way merge commit.
>> -			 * There is no GRAPH_PRE_COMMIT stage for 2-way
>> +			 * This is either a right-skewed 2-way merge
>> +			 * commit, or a left-skewed 3-way merge.
>> +			 * There is no GRAPH_PRE_COMMIT stage for such
>>  			 * merges, so this is the first line of output
>>  			 * for this commit.  Check to see what the previous
>>  			 * line of output was.
>> @@ -960,6 +1006,7 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>>  			 * makes the output look nicer.
>>  			 */
>>  			if (graph->prev_state == GRAPH_POST_MERGE &&
>> +			    graph->prev_edges_added > 0 &&
>>  			    graph->prev_commit_index < i)
>>  				strbuf_write_column(sb, col, '\\');
>>  			else
>> @@ -1031,8 +1078,14 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
>>  				else
>>  					idx++;
>>  			}
>> +			if (graph->edges_added == 0)
>> +				strbuf_addch(sb, ' ');
>> +
>>  		} else if (seen_this) {
>> -			strbuf_write_column(sb, col, '\\');
>> +			if (graph->edges_added > 0)
>> +				strbuf_write_column(sb, col, '\\');
>> +			else
>> +				strbuf_write_column(sb, col, '|');
>>  			strbuf_addch(sb, ' ');
>>  		} else {
>>  			strbuf_write_column(sb, col, '|');
>> diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
>> index cfaba40f97..e479d6e676 100755
>> --- a/t/t4215-log-skewed-merges.sh
>> +++ b/t/t4215-log-skewed-merges.sh
>> @@ -39,4 +39,155 @@ test_expect_success 'log --graph with left-skewed merge' '
>>  	test_cmp expect actual
>>  '
>>  
>> +test_expect_success 'setup nested left-skewed merge' '
>> +	git checkout --orphan 1_p &&
>> +	test_commit 1_A &&
>> +	test_commit 1_B &&
>> +	test_commit 1_C &&
>> +	git checkout -b 1_q @^ && test_commit 1_D &&
>> +	git checkout 1_p && git merge --no-ff 1_q -m 1_E &&
>> +	git checkout -b 1_r @~3 && test_commit 1_F &&
>> +	git checkout 1_p && git merge --no-ff 1_r -m 1_G &&
>> +	git checkout @^^ && git merge --no-ff 1_p -m 1_H
>> +'
>> +
>> +cat > expect <<\EOF
>> +*   1_H
>> +|\
>> +| *   1_G
>> +| |\
>> +| | * 1_F
>> +| * | 1_E
>> +|/| |
>> +| * | 1_D
>> +* | | 1_C
>> +|/ /
>> +* | 1_B
>> +|/
>> +* 1_A
>> +EOF
>> +
>> +test_expect_success 'log --graph with nested left-skewed merge' '
>> +	git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual &&
>> +	test_cmp expect actual
>> +'
> 
> I should have noticed in your earlier commits, but why don't you keep
> the output inside the test suite? You can start with "cat >expect <<-EOF"
> to have it ignore leading whitespace. Sorry if there's something else about
> this that is causing issues.

I was following a pattern used in t/t4202-log.sh. I believe it was easier to debug these tests with the setup and expectations split into separate blocks, but I wouldn't be opposed to merging them.

>> +
>> +test_expect_success 'setup nested left-skewed merge following normal merge' '
>> +	git checkout --orphan 2_p &&
>> +	test_commit 2_A &&
>> +	test_commit 2_B &&
>> +	test_commit 2_C &&
>> +	git checkout -b 2_q @^^ &&
>> +	test_commit 2_D &&
>> +	test_commit 2_E &&
>> +	git checkout -b 2_r @^ && test_commit 2_F &&
>> +	git checkout 2_q &&
>> +	git merge --no-ff 2_r -m 2_G &&
>> +	git merge --no-ff 2_p^ -m 2_H &&
>> +	git checkout -b 2_s @^^ && git merge --no-ff 2_q -m 2_J &&
>> +	git checkout 2_p && git merge --no-ff 2_s -m 2_K
>> +'
>> +
>> +cat > expect <<\EOF
>> +*   2_K
>> +|\
>> +| *   2_J
>> +| |\
>> +| | *   2_H
>> +| | |\
>> +| | * | 2_G
>> +| |/| |
>> +| | * | 2_F
>> +| * | | 2_E
>> +| |/ /
>> +| * | 2_D
>> +* | | 2_C
>> +| |/
>> +|/|
>> +* | 2_B
>> +|/
>> +* 2_A
>> +EOF
>> +
>> +test_expect_success 'log --graph with nested left-skewed merge following normal merge' '
>> +	git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual &&
>> +	test_cmp expect actual
>> +'
>> +
>> +test_expect_success 'setup nested right-skewed merge following left-skewed merge' '
>> +	git checkout --orphan 3_p &&
>> +	test_commit 3_A &&
>> +	git checkout -b 3_q &&
>> +	test_commit 3_B &&
>> +	test_commit 3_C &&
>> +	git checkout -b 3_r @^ &&
>> +	test_commit 3_D &&
>> +	git checkout 3_q && git merge --no-ff 3_r -m 3_E &&
>> +	git checkout 3_p && git merge --no-ff 3_q -m 3_F &&
>> +	git checkout 3_r && test_commit 3_G &&
>> +	git checkout 3_p && git merge --no-ff 3_r -m 3_H &&
>> +	git checkout @^^ && git merge --no-ff 3_p -m 3_J
>> +'
>> +
>> +cat > expect <<\EOF
>> +*   3_J
>> +|\
>> +| *   3_H
>> +| |\
>> +| | * 3_G
>> +| * | 3_F
>> +|/| |
>> +| * |   3_E
>> +| |\ \
>> +| | |/
>> +| | * 3_D
>> +| * | 3_C
>> +| |/
>> +| * 3_B
>> +|/
>> +* 3_A
>> +EOF
>> +
>> +test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge' '
>> +	git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual &&
>> +	test_cmp expect actual
>> +'
>> +
>> +test_expect_success 'setup right-skewed merge following a left-skewed one' '
>> +	git checkout --orphan 4_p &&
>> +	test_commit 4_A &&
>> +	test_commit 4_B &&
>> +	test_commit 4_C &&
>> +	git checkout -b 4_q @^^ && test_commit 4_D &&
>> +	git checkout -b 4_r 4_p^ && git merge --no-ff 4_q -m 4_E &&
>> +	git checkout -b 4_s 4_p^^ &&
>> +	git merge --no-ff 4_r -m 4_F &&
>> +	git merge --no-ff 4_p -m 4_G &&
>> +	git checkout @^^ && git merge --no-ff 4_s -m 4_H
>> +'
>> +
>> +cat > expect <<\EOF
>> +*   4_H
>> +|\
>> +| *   4_G
>> +| |\
>> +| * | 4_F
>> +|/| |
>> +| * |   4_E
>> +| |\ \
>> +| | * | 4_D
>> +| |/ /
>> +|/| |
>> +| | * 4_C
>> +| |/
>> +| * 4_B
>> +|/
>> +* 4_A
>> +EOF
>> +
>> +test_expect_success 'log --graph with right-skewed merge following a left-skewed one' '
>> +	git log --graph --date-order --pretty=tformat:%s | sed "s/ *$//" > actual &&
>> +	test_cmp expect actual
>> +'
>> +
>>  test_done
>>
>
Jeff King Oct. 13, 2019, 6:56 a.m. UTC | #3
On Fri, Oct 11, 2019 at 06:04:21PM +0100, James Coglan wrote:

> > I should have noticed in your earlier commits, but why don't you keep
> > the output inside the test suite? You can start with "cat >expect <<-EOF"
> > to have it ignore leading whitespace. Sorry if there's something else about
> > this that is causing issues.
> 
> I was following a pattern used in t/t4202-log.sh. I believe it was
> easier to debug these tests with the setup and expectations split into
> separate blocks, but I wouldn't be opposed to merging them.

Some of the older tests used that style, but we've been slowly
modernizing (I know, it's hard to pick up the style by example in such
cases!). The usual style these days is making sure everything goes in a
test_expect_* block, with "<<-" to indent here-documents.

Another minor style nit that you picked up from t4202:

> >> +cat > expect <<\EOF

We'd omit the space after ">" here.

-Peff
James Coglan Oct. 14, 2019, 3:38 p.m. UTC | #4
On 13/10/2019 07:56, Jeff King wrote:
> On Fri, Oct 11, 2019 at 06:04:21PM +0100, James Coglan wrote:
> 
>>> I should have noticed in your earlier commits, but why don't you keep
>>> the output inside the test suite? You can start with "cat >expect <<-EOF"
>>> to have it ignore leading whitespace. Sorry if there's something else about
>>> this that is causing issues.
>>
>> I was following a pattern used in t/t4202-log.sh. I believe it was
>> easier to debug these tests with the setup and expectations split into
>> separate blocks, but I wouldn't be opposed to merging them.
> 
> Some of the older tests used that style, but we've been slowly
> modernizing (I know, it's hard to pick up the style by example in such
> cases!). The usual style these days is making sure everything goes in a
> test_expect_* block, with "<<-" to indent here-documents.
> 
> Another minor style nit that you picked up from t4202:
> 
>>>> +cat > expect <<\EOF
> 
> We'd omit the space after ">" here.

Thanks, I've now made the style changes you've suggested on my branch. How should I go about sharing the current state of my patch series after I've incorporated all the changes suggested here? Should I post them as replies on this thread, or start a new pull request via GitGitGadget?
Derrick Stolee Oct. 14, 2019, 5:41 p.m. UTC | #5
On 10/14/2019 11:38 AM, James Coglan wrote:
> On 13/10/2019 07:56, Jeff King wrote:
>> On Fri, Oct 11, 2019 at 06:04:21PM +0100, James Coglan wrote:
>>
>>>> I should have noticed in your earlier commits, but why don't you keep
>>>> the output inside the test suite? You can start with "cat >expect <<-EOF"
>>>> to have it ignore leading whitespace. Sorry if there's something else about
>>>> this that is causing issues.
>>>
>>> I was following a pattern used in t/t4202-log.sh. I believe it was
>>> easier to debug these tests with the setup and expectations split into
>>> separate blocks, but I wouldn't be opposed to merging them.
>>
>> Some of the older tests used that style, but we've been slowly
>> modernizing (I know, it's hard to pick up the style by example in such
>> cases!). The usual style these days is making sure everything goes in a
>> test_expect_* block, with "<<-" to indent here-documents.
>>
>> Another minor style nit that you picked up from t4202:
>>
>>>>> +cat > expect <<\EOF
>>
>> We'd omit the space after ">" here.
> 
> Thanks, I've now made the style changes you've suggested on my branch. How should I go about sharing the current state of my patch series after I've incorporated all the changes suggested here? Should I post them as replies on this thread, or start a new pull request via GitGitGadget?

Since you sent v1 via GitGitGadget, all you need to do is
add another "/submit" comment on the same PR and it will
send a v2 to this thread.

It will auto-generate the range-diff from v1 and append it
to your cover letter.

-Stolee
Johannes Schindelin Oct. 14, 2019, 8:42 p.m. UTC | #6
Hi James,

On Mon, 14 Oct 2019, James Coglan wrote:

> [...] How should I go about sharing the current state of my patch
> series after I've incorporated all the changes suggested here? Should
> I post them as replies on this thread, or start a new pull request via
> GitGitGadget?

Just force-push the branch, and tell GitGitGadget to `/submit`. It will
take care of tagging a new iteration, generating a range-diff, and
sending it off to the list.

Thanks,
Dscho

Patch
diff mbox series

diff --git a/graph.c b/graph.c
index 9136173e03..fb2e42850f 100644
--- a/graph.c
+++ b/graph.c
@@ -197,6 +197,46 @@  struct git_graph {
 	 * 		|/| | | | |		| | | | | *
 	 */
 	int merge_layout;
+	/*
+	 * The number of columns added to the graph by the current commit. For
+	 * 2-way and octopus merges, this is is usually one less than the
+	 * number of parents:
+	 *
+	 * 		| | |			| |    \
+	 *		| * |			| *---. \
+	 *		| |\ \			| |\ \ \ \
+	 *		| | | |         	| | | | | |
+	 *
+	 *		num_parents: 2		num_parents: 4
+	 *		edges_added: 1		edges_added: 3
+	 *
+	 * For left-skewed merges, the first parent fuses with its neighbor and
+	 * so one less column is added:
+	 *
+	 *		| | |			| |  \
+	 *		| * |			| *-. \
+	 *		|/| |			|/|\ \ \
+	 *		| | |			| | | | |
+	 *
+	 *		num_parents: 2		num_parents: 4
+	 *		edges_added: 0		edges_added: 2
+	 *
+	 * This number determines how edges to the right of the merge are
+	 * displayed in commit and post-merge lines; if no columns have been
+	 * added then a vertical line should be used where a right-tracking
+	 * line would otherwise be used.
+	 *
+	 *		| * \			| * |
+	 *		| |\ \			|/| |
+	 *		| | * \			| * |
+	 */
+	int edges_added;
+	/*
+	 * The number of columns added by the previous commit, which is used to
+	 * smooth edges appearing to the right of a commit in a commit line
+	 * following a post-merge line.
+	 */
+	int prev_edges_added;
 	/*
 	 * The maximum number of columns that can be stored in the columns
 	 * and new_columns arrays.  This is also half the number of entries
@@ -309,6 +349,8 @@  struct git_graph *graph_init(struct rev_info *opt)
 	graph->commit_index = 0;
 	graph->prev_commit_index = 0;
 	graph->merge_layout = 0;
+	graph->edges_added = 0;
+	graph->prev_edges_added = 0;
 	graph->num_columns = 0;
 	graph->num_new_columns = 0;
 	graph->mapping_size = 0;
@@ -670,6 +712,9 @@  void graph_update(struct git_graph *graph, struct commit *commit)
 	 */
 	graph_update_columns(graph);
 
+	graph->prev_edges_added = graph->edges_added;
+	graph->edges_added = graph->num_parents + graph->merge_layout - 2;
+
 	graph->expansion_row = 0;
 
 	/*
@@ -943,12 +988,13 @@  static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 
 			if (graph->num_parents > 2)
 				graph_draw_octopus_merge(graph, sb);
-		} else if (seen_this && (graph->num_parents > 2)) {
+		} else if (seen_this && (graph->edges_added > 1)) {
 			strbuf_write_column(sb, col, '\\');
-		} else if (seen_this && (graph->num_parents == 2)) {
+		} else if (seen_this && (graph->edges_added == 1)) {
 			/*
-			 * This is a 2-way merge commit.
-			 * There is no GRAPH_PRE_COMMIT stage for 2-way
+			 * This is either a right-skewed 2-way merge
+			 * commit, or a left-skewed 3-way merge.
+			 * There is no GRAPH_PRE_COMMIT stage for such
 			 * merges, so this is the first line of output
 			 * for this commit.  Check to see what the previous
 			 * line of output was.
@@ -960,6 +1006,7 @@  static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 			 * makes the output look nicer.
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
+			    graph->prev_edges_added > 0 &&
 			    graph->prev_commit_index < i)
 				strbuf_write_column(sb, col, '\\');
 			else
@@ -1031,8 +1078,14 @@  static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 				else
 					idx++;
 			}
+			if (graph->edges_added == 0)
+				strbuf_addch(sb, ' ');
+
 		} else if (seen_this) {
-			strbuf_write_column(sb, col, '\\');
+			if (graph->edges_added > 0)
+				strbuf_write_column(sb, col, '\\');
+			else
+				strbuf_write_column(sb, col, '|');
 			strbuf_addch(sb, ' ');
 		} else {
 			strbuf_write_column(sb, col, '|');
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index cfaba40f97..e479d6e676 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -39,4 +39,155 @@  test_expect_success 'log --graph with left-skewed merge' '
 	test_cmp expect actual
 '
 
+test_expect_success 'setup nested left-skewed merge' '
+	git checkout --orphan 1_p &&
+	test_commit 1_A &&
+	test_commit 1_B &&
+	test_commit 1_C &&
+	git checkout -b 1_q @^ && test_commit 1_D &&
+	git checkout 1_p && git merge --no-ff 1_q -m 1_E &&
+	git checkout -b 1_r @~3 && test_commit 1_F &&
+	git checkout 1_p && git merge --no-ff 1_r -m 1_G &&
+	git checkout @^^ && git merge --no-ff 1_p -m 1_H
+'
+
+cat > expect <<\EOF
+*   1_H
+|\
+| *   1_G
+| |\
+| | * 1_F
+| * | 1_E
+|/| |
+| * | 1_D
+* | | 1_C
+|/ /
+* | 1_B
+|/
+* 1_A
+EOF
+
+test_expect_success 'log --graph with nested left-skewed merge' '
+	git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'setup nested left-skewed merge following normal merge' '
+	git checkout --orphan 2_p &&
+	test_commit 2_A &&
+	test_commit 2_B &&
+	test_commit 2_C &&
+	git checkout -b 2_q @^^ &&
+	test_commit 2_D &&
+	test_commit 2_E &&
+	git checkout -b 2_r @^ && test_commit 2_F &&
+	git checkout 2_q &&
+	git merge --no-ff 2_r -m 2_G &&
+	git merge --no-ff 2_p^ -m 2_H &&
+	git checkout -b 2_s @^^ && git merge --no-ff 2_q -m 2_J &&
+	git checkout 2_p && git merge --no-ff 2_s -m 2_K
+'
+
+cat > expect <<\EOF
+*   2_K
+|\
+| *   2_J
+| |\
+| | *   2_H
+| | |\
+| | * | 2_G
+| |/| |
+| | * | 2_F
+| * | | 2_E
+| |/ /
+| * | 2_D
+* | | 2_C
+| |/
+|/|
+* | 2_B
+|/
+* 2_A
+EOF
+
+test_expect_success 'log --graph with nested left-skewed merge following normal merge' '
+	git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'setup nested right-skewed merge following left-skewed merge' '
+	git checkout --orphan 3_p &&
+	test_commit 3_A &&
+	git checkout -b 3_q &&
+	test_commit 3_B &&
+	test_commit 3_C &&
+	git checkout -b 3_r @^ &&
+	test_commit 3_D &&
+	git checkout 3_q && git merge --no-ff 3_r -m 3_E &&
+	git checkout 3_p && git merge --no-ff 3_q -m 3_F &&
+	git checkout 3_r && test_commit 3_G &&
+	git checkout 3_p && git merge --no-ff 3_r -m 3_H &&
+	git checkout @^^ && git merge --no-ff 3_p -m 3_J
+'
+
+cat > expect <<\EOF
+*   3_J
+|\
+| *   3_H
+| |\
+| | * 3_G
+| * | 3_F
+|/| |
+| * |   3_E
+| |\ \
+| | |/
+| | * 3_D
+| * | 3_C
+| |/
+| * 3_B
+|/
+* 3_A
+EOF
+
+test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge' '
+	git log --graph --pretty=tformat:%s | sed "s/ *$//" > actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'setup right-skewed merge following a left-skewed one' '
+	git checkout --orphan 4_p &&
+	test_commit 4_A &&
+	test_commit 4_B &&
+	test_commit 4_C &&
+	git checkout -b 4_q @^^ && test_commit 4_D &&
+	git checkout -b 4_r 4_p^ && git merge --no-ff 4_q -m 4_E &&
+	git checkout -b 4_s 4_p^^ &&
+	git merge --no-ff 4_r -m 4_F &&
+	git merge --no-ff 4_p -m 4_G &&
+	git checkout @^^ && git merge --no-ff 4_s -m 4_H
+'
+
+cat > expect <<\EOF
+*   4_H
+|\
+| *   4_G
+| |\
+| * | 4_F
+|/| |
+| * |   4_E
+| |\ \
+| | * | 4_D
+| |/ /
+|/| |
+| | * 4_C
+| |/
+| * 4_B
+|/
+* 4_A
+EOF
+
+test_expect_success 'log --graph with right-skewed merge following a left-skewed one' '
+	git log --graph --date-order --pretty=tformat:%s | sed "s/ *$//" > actual &&
+	test_cmp expect actual
+'
+
 test_done