[2/2] graph: fix collapse of multiple edges
diff mbox series

Message ID 12abb32531ed7125293986dc139a7ffed3839065.1578457675.git.gitgitgadget@gmail.com
State New
Headers show
Series
  • Graph horizontal fix
Related show

Commit Message

Han-Wen Nienhuys via GitGitGadget Jan. 8, 2020, 4:27 a.m. UTC
From: Derrick Stolee <dstolee@microsoft.com>

This fix resolves the previously-added test_expect_failure in
t4215-log-skewed-merges.sh.

The issue lies in the "else" condition while updating the mapping
inside graph_output_collapsing_line(). In 0f0f389f (graph: tidy up
display of left-skewed merges, 2019-10-15), the output of left-
skewed merges was changed to allow an immediate horizontal edge in
the first parent, output by graph_output_post_merge_line() instead
of by graph_output_collapsing_line(). This condensed the first line
behavior as follows:

Before 0f0f389f:

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

After 0f0f389f:

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

However, a very subtle issue arose when the second and third parent
edges are collapsed in later steps. The second parent edge is now
immediately adjacent to a vertical edge. This means that the
condition

	} else if (graph->mapping[i - 1] < 0) {

in graph_output_collapsing_line() evaluates as false. The block for
this condition was the only place where we connected the target
column with the current position with horizontal edge markers.

In this case, the final "else" block is run, and the edge is marked
as horizontal, but did not back-fill the blank columns between the
target and the current edge. Since the second parent edge is marked
as horizontal, the third parent edge is not marked as horizontal.
This causes the output to continue as follows:

Before this change:

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

By adding the logic for "filling" a horizontal edge between the
target column and the current column, we are able to resolve the
issue.

After this change:

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

This output properly matches the expected blend of the edge
behavior before 0f0f389f and the merge commit rendering from
0f0f389f.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 graph.c                      | 10 ++++++++--
 t/t4215-log-skewed-merges.sh |  2 +-
 2 files changed, 9 insertions(+), 3 deletions(-)

Comments

Jeff King Jan. 8, 2020, 7:25 a.m. UTC | #1
On Wed, Jan 08, 2020 at 04:27:55AM +0000, Derrick Stolee via GitGitGadget wrote:

> Before this change:
> 
> 	| | | | | | *
> 	| |_|_|_|_|/|\
> 	|/| | | | |/ /
> 	| | | | |/| /
> 	| | | |/| |/
> 	| | |/| |/|
> 	| |/| |/| |
> 	| | |/| | |
> 
> By adding the logic for "filling" a horizontal edge between the
> target column and the current column, we are able to resolve the
> issue.
> 
> After this change:
> 
> 	| | | | | | *
> 	| |_|_|_|_|/|\
> 	|/| | | | |/ /
> 	| | |_|_|/| /
> 	| |/| | | |/
> 	| | | |_|/|
> 	| | |/| | |

Hmm. Your description and your diagrams make sense to me. But one
curious thing is that the earlier test you added for 6_* does not need
modified. Because it continues to show:

          | | | | * 6_F
          | |_|_|/|
          |/| | |/
          | | |/|
          | |/| |
          | * | | 6_D

rather than adding a horizontal component to the second-parent line.
That seems inconsistent.

-Peff
Derrick Stolee Jan. 8, 2020, 1:40 p.m. UTC | #2
On 1/8/2020 2:25 AM, Jeff King wrote:
> On Wed, Jan 08, 2020 at 04:27:55AM +0000, Derrick Stolee via GitGitGadget wrote:
> 
>> Before this change:
>>
>> 	| | | | | | *
>> 	| |_|_|_|_|/|\
>> 	|/| | | | |/ /
>> 	| | | | |/| /
>> 	| | | |/| |/
>> 	| | |/| |/|
>> 	| |/| |/| |
>> 	| | |/| | |
>>
>> By adding the logic for "filling" a horizontal edge between the
>> target column and the current column, we are able to resolve the
>> issue.
>>
>> After this change:
>>
>> 	| | | | | | *
>> 	| |_|_|_|_|/|\
>> 	|/| | | | |/ /
>> 	| | |_|_|/| /
>> 	| |/| | | |/
>> 	| | | |_|/|
>> 	| | |/| | |
> 
> Hmm. Your description and your diagrams make sense to me. But one
> curious thing is that the earlier test you added for 6_* does not need
> modified. Because it continues to show:
> 
>           | | | | * 6_F
>           | |_|_|/|
>           |/| | |/
>           | | |/|
>           | |/| |
>           | * | | 6_D
> 
> rather than adding a horizontal component to the second-parent line.
> That seems inconsistent.

The issue here is that there is not enough room for a second horizontal
line. The horizontal line can only start after the previous has completely
terminated, that is

           | | | | * 6_F
           | |_|_|/|
           |/| | |/

at this point, the first horizontal line has terminated.

           | | |/|
           | |/| |

The remaining movement for the second line has no room for a horizontal
edge. The logic that I added is hit, but the for loop (over j) terminates
immediately without a single execution of the loop body.

If there was one more row to the example, then we would have:

           | | | | | * 6_F
           | |_|_|_|/|
           |/| | | |/
           | | |_|/|
           | |/| | |
           | * | | | 6_D

Thanks,
-Stolee
Jeff King Jan. 8, 2020, 1:49 p.m. UTC | #3
On Wed, Jan 08, 2020 at 08:40:26AM -0500, Derrick Stolee wrote:

> > Hmm. Your description and your diagrams make sense to me. But one
> > curious thing is that the earlier test you added for 6_* does not need
> > modified. Because it continues to show:
> > 
> >           | | | | * 6_F
> >           | |_|_|/|
> >           |/| | |/
> >           | | |/|
> >           | |/| |
> >           | * | | 6_D
> > 
> > rather than adding a horizontal component to the second-parent line.
> > That seems inconsistent.
> 
> The issue here is that there is not enough room for a second horizontal
> line. The horizontal line can only start after the previous has completely
> terminated, that is
> 
>            | | | | * 6_F
>            | |_|_|/|
>            |/| | |/
> 
> at this point, the first horizontal line has terminated.

Ahhh, OK, that makes perfect sense. I didn't quite realize how the rules
for "going horizontal" worked.

> If there was one more row to the example, then we would have:
> 
>            | | | | | * 6_F
>            | |_|_|_|/|
>            |/| | | |/
>            | | |_|/|
>            | |/| | |
>            | * | | | 6_D

Right, that makes sense. Thanks for explaining. And the patch otherwise
looked good to me; your explanation convinced me that this is the right
thing to do.

-Peff

Patch
diff mbox series

diff --git a/graph.c b/graph.c
index aaf97069bd..4fb25ad464 100644
--- a/graph.c
+++ b/graph.c
@@ -1233,8 +1233,14 @@  static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 			 * prevent any other edges from moving
 			 * horizontally.
 			 */
-			if (horizontal_edge == -1)
-				horizontal_edge = i;
+			if (horizontal_edge == -1) {
+				int j;
+				horizontal_edge_target = target;
+				horizontal_edge = i - 1;
+
+				for (j = (target * 2) + 3; j < (i - 2); j += 2)
+					graph->mapping[j] = target;
+			}
 		}
 	}
 
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 099e4b89b4..1d0d3240ff 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -311,7 +311,7 @@  test_expect_success 'log --graph with multiple tips and colors' '
 	test_cmp expect.colors actual.colors
 '
 
-test_expect_failure 'log --graph with multiple tips' '
+test_expect_success 'log --graph with multiple tips' '
 	git checkout --orphan 7_1 &&
 	test_commit 7_A &&
 	test_commit 7_B &&