[v3,08/13] graph: tidy up display of left-skewed merges

Commit Message

Linus Arver via GitGitGadget Oct. 15, 2019, 11:47 p.m. UTC

From: James Coglan <[e-mail]>

Currently, when we display a merge whose first parent is already present
in a column to the left of the merge commit, we display the first parent
as a vertical pipe `|` in the GRAPH_POST_MERGE line and then immediately
enter the GRAPH_COLLAPSING state. The first-parent line tracks to the
left and all the other parent lines follow it; this creates a "kink" in
those lines:

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

This change tidies the display of such commits such that if the first
parent appears to the left of the merge, we render it as a `/` and the
second parent as a `|`. This reduces the horizontal and vertical space
needed to render the merge, and makes the resulting lines easier to
read.

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

If the first parent is separated from the merge by several columns, a
horizontal line is drawn in a similar manner to how the GRAPH_COLLAPSING
state displays the line.

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

This effect is applied to both "normal" two-parent merges, and to
octopus merges. It also reduces the vertical space needed for pre-commit
lines, as the merge occupies one less column than usual.

        Before:         After:

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

Signed-off-by: James Coglan <[e-mail]>
---
 graph.c                      | 125 +++++++++++++++++++++++++++--------
 t/t4214-log-graph-octopus.sh |  20 +++---
 t/t4215-log-skewed-merges.sh |  45 +++++++++++--
 3 files changed, 144 insertions(+), 46 deletions(-)

Comments

Junio C Hamano Oct. 16, 2019, 4 a.m. UTC | #1

"James Coglan via GitGitGadget" <[e-mail]> writes:

> This effect is applied to both "normal" two-parent merges, and to
> octopus merges. It also reduces the vertical space needed for pre-commit
> lines, as the merge occupies one less column than usual.
>
>         Before:         After:
>
>         | *             | *
>         | |\            | |\
>         | | \           | * \
>         | |  \          |/|\ \
>         | *-. \
>         | |\ \ \

Looking at these drawings reminded me of a tangent that is brought
up from time to time.  We do not do great job when showing multiple
roots.

If you have a history like this:

      A---D---E
         /
    B---C

drawing the graph _with_ the merge gives a reasonable representation
of the entire topology.

    * 46f67dd E
    *   6f89516 D
    |\  
    | * e6277a9 C
    | * 13ae9b2 B
    * afee005 A

But if you start drawing from parents of D (excluding D), you'd get
this:

    * e6277a9 C
    * 13ae9b2 B
    * afee005 A

and the fact that B and A do not share parent-child relationships is
lost.  An easy way to show that would be to draw the bottom three
lines of the full history output we saw earlier:

    | * e6277a9 C
    | * 13ae9b2 B
    * afee005 A

either with or without the vertical bar to imply that A may have a
child.

This is not something that has to be done as part of this series,
but I am hoping that the internal simplification and code
restructuring that is done by this series would make it easier to
enhance the system to allow such an output.

Thanks.

Derrick Stolee Oct. 17, 2019, 12:34 p.m. UTC | #2

On 10/16/2019 12:00 AM, Junio C Hamano wrote:
> "James Coglan via GitGitGadget" <[e-mail]> writes:
> 
>> This effect is applied to both "normal" two-parent merges, and to
>> octopus merges. It also reduces the vertical space needed for pre-commit
>> lines, as the merge occupies one less column than usual.
>>
>>         Before:         After:
>>
>>         | *             | *
>>         | |\            | |\
>>         | | \           | * \
>>         | |  \          |/|\ \
>>         | *-. \
>>         | |\ \ \
> 
> Looking at these drawings reminded me of a tangent that is brought
> up from time to time.  We do not do great job when showing multiple
> roots.
> 
> If you have a history like this:
> 
>       A---D---E
>          /
>     B---C
> 
> drawing the graph _with_ the merge gives a reasonable representation
> of the entire topology.
> 
>     * 46f67dd E
>     *   6f89516 D
>     |\  
>     | * e6277a9 C
>     | * 13ae9b2 B
>     * afee005 A
> 
> But if you start drawing from parents of D (excluding D), you'd get
> this:
> 
>     * e6277a9 C
>     * 13ae9b2 B
>     * afee005 A

I hit this very situation recently when I was experimenting with
'git fast-import' and accidentally created many parallel, independent
histories. Running "git log --graph --all --simplify-by-decoration"
made it look like all the refs were in a line, but they were not.
(The one way I knew something was up: the base commits also appeared
without a decoration. That was the only clue that the histories did
not continue in a line.)

> 
> and the fact that B and A do not share parent-child relationships is
> lost.  An easy way to show that would be to draw the bottom three
> lines of the full history output we saw earlier:
> 
>     | * e6277a9 C
>     | * 13ae9b2 B
>     * afee005 A
> 
> either with or without the vertical bar to imply that A may have a
> child.
The natural extension of this would be multiple columns:

 | | | | | *
 | | | | *
 | | | *
 | | *
 | *
 *

This does not appear too cumbersome, and such a situation should
be rare.

> This is not something that has to be done as part of this series,
> but I am hoping that the internal simplification and code
> restructuring that is done by this series would make it easier to
> enhance the system to allow such an output.

I agree. An excellent idea for a follow-up.

Thanks,
-Stolee

Junio C Hamano Oct. 18, 2019, 12:49 a.m. UTC | #3

Derrick Stolee <[e-mail]> writes:

> I hit this very situation recently when I was experimenting with
> 'git fast-import' and accidentally created many parallel, independent
> histories. Running "git log --graph --all --simplify-by-decoration"
> made it look like all the refs were in a line, but they were not.
> (The one way I knew something was up: the base commits also appeared
> without a decoration. That was the only clue that the histories did
> not continue in a line.)
>
>> 
>> and the fact that B and A do not share parent-child relationships is
>> lost.  An easy way to show that would be to draw the bottom three
>> lines of the full history output we saw earlier:
>> 
>>     | * e6277a9 C
>>     | * 13ae9b2 B
>>     * afee005 A
>> 
>> either with or without the vertical bar to imply that A may have a
>> child.
> The natural extension of this would be multiple columns:
>
>  | | | | | *
>  | | | | *
>  | | | *
>  | | *
>  | *
>  *

After sleeping over it, I now think we shouldn't draw lines that
imply a child for each of these commits, as we haven't seen, but
I agree that this can be extended to 3 or more roots.

Patch

diff --git a/graph.c b/graph.c
index bd7403065e..e37127f5ab 100644
--- a/graph.c
+++ b/graph.c
@@ -202,6 +202,20 @@  struct git_graph {
 	 * previous commit.
 	 */
 	int prev_commit_index;
+	/*
+	 * Which layout variant to use to display merge commits. If the
+	 * commit's first parent is known to be in a column to the left of the
+	 * merge, then this value is 0 and we use the layout on the left.
+	 * Otherwise, the value is 1 and the layout on the right is used. This
+	 * field tells us how many columns the first parent occupies.
+	 *
+	 * 		0)			1)
+	 *
+	 * 		| | | *-.		| | *---.
+	 * 		| |_|/|\ \		| | |\ \ \
+	 * 		|/| | | | |		| | | | | *
+	 */
+	int merge_layout;
 	/*
 	 * The maximum number of columns that can be stored in the columns
 	 * and new_columns arrays.  This is also half the number of entries
@@ -313,6 +327,7 @@  struct git_graph *graph_init(struct rev_info *opt)
 	graph->prev_state = GRAPH_PADDING;
 	graph->commit_index = 0;
 	graph->prev_commit_index = 0;
+	graph->merge_layout = 0;
 	graph->num_columns = 0;
 	graph->num_new_columns = 0;
 	graph->mapping_size = 0;
@@ -472,9 +487,11 @@  static int graph_find_new_column_by_commit(struct git_graph *graph,
 }
 
 static void graph_insert_into_new_columns(struct git_graph *graph,
-					  struct commit *commit)
+					  struct commit *commit,
+					  int idx)
 {
 	int i = graph_find_new_column_by_commit(graph, commit);
+	int mapping_idx;
 
 	/*
 	 * If the commit is not already in the new_columns array, then add it
@@ -486,8 +503,26 @@  static void graph_insert_into_new_columns(struct git_graph *graph,
 		graph->new_columns[i].color = graph_find_commit_color(graph, commit);
 	}
 
-	graph->mapping[graph->width] = i;
-	graph->width += 2;
+	if (graph->num_parents > 1 && idx > -1 && graph->merge_layout == -1) {
+		/*
+		 * If this is the first parent of a merge, choose a layout for
+		 * the merge line based on whether the parent appears in a
+		 * column to the left of the merge
+		 */
+		int dist, shift;
+
+		dist = idx - i;
+		shift = (dist > 1) ? 2 * dist - 3 : 1;
+
+		graph->merge_layout = (dist > 0) ? 0 : 1;
+		mapping_idx = graph->width + (graph->merge_layout - 1) * shift;
+		graph->width += 2 * graph->merge_layout;
+	} else {
+		mapping_idx = graph->width;
+		graph->width += 2;
+	}
+
+	graph->mapping[mapping_idx] = i;
 }
 
 static void graph_update_columns(struct git_graph *graph)
@@ -553,6 +588,7 @@  static void graph_update_columns(struct git_graph *graph)
 		if (col_commit == graph->commit) {
 			seen_this = 1;
 			graph->commit_index = i;
+			graph->merge_layout = -1;
 			for (parent = first_interesting_parent(graph);
 			     parent;
 			     parent = next_interesting_parent(graph, parent)) {
@@ -565,7 +601,7 @@  static void graph_update_columns(struct git_graph *graph)
 				    !is_commit_in_columns) {
 					graph_increment_column_color(graph);
 				}
-				graph_insert_into_new_columns(graph, parent->item);
+				graph_insert_into_new_columns(graph, parent->item, i);
 			}
 			/*
 			 * We always need to increment graph->width by at
@@ -576,7 +612,7 @@  static void graph_update_columns(struct git_graph *graph)
 			if (graph->num_parents == 0)
 				graph->width += 2;
 		} else {
-			graph_insert_into_new_columns(graph, col_commit);
+			graph_insert_into_new_columns(graph, col_commit, -1);
 		}
 	}
 
@@ -588,10 +624,36 @@  static void graph_update_columns(struct git_graph *graph)
 		graph->mapping_size--;
 }
 
+static int graph_num_expansion_rows(struct git_graph *graph)
+{
+	/*
+	 * Normally, we need two expansion rows for each dashed parent line from
+	 * an octopus merge:
+	 *
+	 * 		| *
+	 * 		| |\
+	 * 		| | \
+	 * 		| |  \
+	 * 		| *-. \
+	 * 		| |\ \ \
+	 *
+	 * If the merge is skewed to the left, then its parents occupy one less
+	 * column, and we don't need as many expansion rows to route around it;
+	 * in some cases that means we don't need any expansion rows at all:
+	 *
+	 * 		| *
+	 * 		| |\
+	 * 		| * \
+	 * 		|/|\ \
+	 */
+	return (graph->num_parents + graph->merge_layout - 3) * 2;
+}
+
 static int graph_needs_pre_commit_line(struct git_graph *graph)
 {
 	return graph->num_parents >= 3 &&
-	       graph->commit_index < (graph->num_columns - 1);
+	       graph->commit_index < (graph->num_columns - 1) &&
+	       graph->expansion_row < graph_num_expansion_rows(graph);
 }
 
 void graph_update(struct git_graph *graph, struct commit *commit)
@@ -728,7 +790,6 @@  static void graph_output_skip_line(struct git_graph *graph, struct graph_line *l
 static void graph_output_pre_commit_line(struct git_graph *graph,
 					 struct graph_line *line)
 {
-	int num_expansion_rows;
 	int i, seen_this;
 
 	/*
@@ -739,14 +800,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);
-	num_expansion_rows = (graph->num_parents - 2) * 2;
 
 	/*
 	 * 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->expansion_row < num_expansion_rows);
+	       graph->expansion_row < graph_num_expansion_rows(graph));
 
 	/*
 	 * Output the row
@@ -786,7 +846,7 @@  static void graph_output_pre_commit_line(struct git_graph *graph,
 	 * and move to state GRAPH_COMMIT if necessary
 	 */
 	graph->expansion_row++;
-	if (graph->expansion_row >= num_expansion_rows)
+	if (!graph_needs_pre_commit_line(graph))
 		graph_update_state(graph, GRAPH_COMMIT);
 }
 
@@ -824,7 +884,7 @@  static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line
 	 * x 0 1 2 3
 	 *
 	 */
-	const int dashless_parents = 2;
+	const int dashless_parents = 3 - graph->merge_layout;
 	int dashful_parents = graph->num_parents - dashless_parents;
 
 	/*
@@ -832,9 +892,9 @@  static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line
 	 * above) but sometimes the first parent goes into an existing column,
 	 * like this:
 	 *
-	 * | *---.
-	 * | |\ \ \
-	 * |/ / / /
+	 * | *-.
+	 * |/|\ \
+	 * | | | |
 	 * x 0 1 2
 	 *
 	 * In which case the number of parents will be one greater than the
@@ -925,10 +985,15 @@  static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
+const char merge_chars[] = {'/', '|', '\\'};
+
 static void graph_output_post_merge_line(struct git_graph *graph, struct graph_line *line)
 {
 	int seen_this = 0;
-	int i, j;
+	int i;
+
+	struct commit_list *first_parent = first_interesting_parent(graph);
+	int seen_parent = 0;
 
 	/*
 	 * Output the post-merge row
@@ -951,30 +1016,34 @@  static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 			 * new_columns and use those to format the
 			 * edges.
 			 */
-			struct commit_list *parents = NULL;
+			struct commit_list *parents = first_parent;
 			int par_column;
+			int idx = graph->merge_layout;
+			char c;
 			seen_this = 1;
-			parents = first_interesting_parent(graph);
-			assert(parents);
-			par_column = graph_find_new_column_by_commit(graph, parents->item);
-			assert(par_column >= 0);
-
-			graph_line_write_column(line, &graph->new_columns[par_column], '|');
-			for (j = 0; j < graph->num_parents - 1; j++) {
-				parents = next_interesting_parent(graph, parents);
-				assert(parents);
+
+			for (; parents; parents = next_interesting_parent(graph, parents)) {
 				par_column = graph_find_new_column_by_commit(graph, parents->item);
 				assert(par_column >= 0);
-				graph_line_write_column(line, &graph->new_columns[par_column], '\\');
-				graph_line_addch(line, ' ');
+
+				c = merge_chars[idx];
+				graph_line_write_column(line, &graph->new_columns[par_column], c);
+				if (idx == 2)
+					graph_line_addch(line, ' ');
+				else
+					idx++;
 			}
 		} else if (seen_this) {
 			graph_line_write_column(line, col, '\\');
 			graph_line_addch(line, ' ');
 		} else {
 			graph_line_write_column(line, col, '|');
-			graph_line_addch(line, ' ');
+			if (graph->merge_layout != 0 || i != graph->commit_index - 1)
+				graph_line_addch(line, seen_parent ? '_' : ' ');
 		}
+
+		if (col_commit == first_parent->item)
+			seen_parent = 1;
 	}
 
 	/*
diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh
index 3ae8e51e50..1b96276894 100755
--- a/t/t4214-log-graph-octopus.sh
+++ b/t/t4214-log-graph-octopus.sh
@@ -26,9 +26,8 @@  test_expect_success 'set up merge history' '
 test_expect_success 'log --graph with tricky octopus merge, no color' '
 	cat >expect.uncolored <<-\EOF &&
 	* left
-	| *---.   octopus-merge
-	| |\ \ \
-	|/ / / /
+	| *-.   octopus-merge
+	|/|\ \
 	| | | * 4
 	| | * | 3
 	| | |/
@@ -47,9 +46,8 @@  test_expect_success 'log --graph with tricky octopus merge with colors' '
 	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
 	cat >expect.colors <<-\EOF &&
 	* left
-	<RED>|<RESET> *<BLUE>-<RESET><BLUE>-<RESET><MAGENTA>-<RESET><MAGENTA>.<RESET>   octopus-merge
-	<RED>|<RESET> <RED>|<RESET><YELLOW>\<RESET> <BLUE>\<RESET> <MAGENTA>\<RESET>
-	<RED>|<RESET><RED>/<RESET> <YELLOW>/<RESET> <BLUE>/<RESET> <MAGENTA>/<RESET>
+	<RED>|<RESET> *<MAGENTA>-<RESET><MAGENTA>.<RESET>   octopus-merge
+	<RED>|<RESET><RED>/<RESET><YELLOW>|<RESET><BLUE>\<RESET> <MAGENTA>\<RESET>
 	<RED>|<RESET> <YELLOW>|<RESET> <BLUE>|<RESET> * 4
 	<RED>|<RESET> <YELLOW>|<RESET> * <MAGENTA>|<RESET> 3
 	<RED>|<RESET> <YELLOW>|<RESET> <MAGENTA>|<RESET><MAGENTA>/<RESET>
@@ -147,9 +145,8 @@  test_expect_success 'log --graph with tricky octopus merge and its child, no col
 	cat >expect.uncolored <<-\EOF &&
 	* left
 	| * after-merge
-	| *---.   octopus-merge
-	| |\ \ \
-	|/ / / /
+	| *-.   octopus-merge
+	|/|\ \
 	| | | * 4
 	| | * | 3
 	| | |/
@@ -169,9 +166,8 @@  test_expect_failure 'log --graph with tricky octopus merge and its child with co
 	cat >expect.colors <<-\EOF &&
 	* left
 	<RED>|<RESET> * after-merge
-	<RED>|<RESET> *<MAGENTA>-<RESET><MAGENTA>-<RESET><CYAN>-<RESET><CYAN>.<RESET>   octopus-merge
-	<RED>|<RESET> <RED>|<RESET><BLUE>\<RESET> <MAGENTA>\<RESET> <CYAN>\<RESET>
-	<RED>|<RESET><RED>/<RESET> <BLUE>/<RESET> <MAGENTA>/<RESET> <CYAN>/<RESET>
+	<RED>|<RESET> *<CYAN>-<RESET><CYAN>.<RESET>   octopus-merge
+	<RED>|<RESET><RED>/<RESET><BLUE>|<RESET><MAGENTA>\<RESET> <CYAN>\<RESET>
 	<RED>|<RESET> <BLUE>|<RESET> <MAGENTA>|<RESET> * 4
 	<RED>|<RESET> <BLUE>|<RESET> * <CYAN>|<RESET> 3
 	<RED>|<RESET> <BLUE>|<RESET> <CYAN>|<RESET><CYAN>/<RESET>
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 4582ba066a..dc187b5caf 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -11,12 +11,8 @@  test_expect_success 'log --graph with merge fusing with its left and right neigh
 	| *   G
 	| |\
 	| | * F
-	| | |
-	| |  \
-	| *-. \   E
-	| |\ \ \
-	|/ / / /
-	| | | /
+	| * \   E
+	|/|\ \
 	| | |/
 	| | * D
 	| * | C
@@ -40,4 +36,41 @@  test_expect_success 'log --graph with merge fusing with its left and right neigh
 	test_cmp expect actual
 '
 
+test_expect_success 'log --graph with left-skewed merge' '
+	cat >expect <<-\EOF &&
+	*-----.   0_H
+	|\ \ \ \
+	| | | | * 0_G
+	| |_|_|/|
+	|/| | | |
+	| | | * \   0_F
+	| |_|/|\ \
+	|/| | | |/
+	| | | | * 0_E
+	| |_|_|/
+	|/| | |
+	| | * | 0_D
+	| | |/
+	| | * 0_C
+	| |/
+	|/|
+	| * 0_B
+	|/
+	* 0_A
+	EOF
+
+	git checkout --orphan 0_p && test_commit 0_A &&
+	git checkout -b 0_q 0_p && test_commit 0_B &&
+	git checkout -b 0_r 0_p &&
+	test_commit 0_C &&
+	test_commit 0_D &&
+	git checkout -b 0_s 0_p && test_commit 0_E &&
+	git checkout -b 0_t 0_p && git merge --no-ff 0_r^ 0_s -m 0_F &&
+	git checkout 0_p && git merge --no-ff 0_s -m 0_G &&
+	git checkout @^ && git merge --no-ff 0_q 0_r 0_t 0_p -m 0_H &&
+
+	git log --graph --pretty=tformat:%s | sed "s/ *$//" >actual &&
+	test_cmp expect actual
+'
+
 test_done