[PATCH v6] log: fix coloring of certain octupus merge shapes

[PATCH v6] log: fix coloring of certain octupus merge shapes

[Noam Postavsky]

For octopus merges where the first parent edge immediately merges into
the next column to the left:

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

then the number of columns should be one less than the usual case:

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

Also refactor the code to iterate over columns rather than dashes,
building from an initial patch suggestion by Jeff King.

Signed-off-by: Noam Postavsky <npostavs@users.sourceforge.net>
Reviewed-by: Jeff King <peff@peff.net>
---
 graph.c                      |  56 +++++++++++++++++-------
 t/t4214-log-graph-octopus.sh | 102 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 143 insertions(+), 15 deletions(-)
 create mode 100755 t/t4214-log-graph-octopus.sh

diff --git a/graph.c b/graph.c
index e1f6d3bddb..a3366f6dac 100644
--- a/graph.c
+++ b/graph.c
@@ -842,27 +842,53 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 }
 
 /*
- * Draw an octopus merge and return the number of characters written.
+ * Draw the horizontal dashes of an octopus merge and return the number of
+ * characters written.
  */
 static int graph_draw_octopus_merge(struct git_graph *graph,
 				    struct strbuf *sb)
 {
 	/*
-	 * Here dashless_commits represents the number of parents
-	 * which don't need to have dashes (because their edges fit
-	 * neatly under the commit).
-	 */
-	const int dashless_commits = 2;
-	int col_num, i;
-	int num_dashes =
-		((graph->num_parents - dashless_commits) * 2) - 1;
-	for (i = 0; i < num_dashes; i++) {
-		col_num = (i / 2) + dashless_commits + graph->commit_index;
-		strbuf_write_column(sb, &graph->new_columns[col_num], '-');
+	 * Here dashless_parents represents the number of parents which don't
+	 * need to have dashes (the edges labeled "0" and "1").  And
+	 * dashful_parents are the remaining ones.
+	 *
+	 * | *---.
+	 * | |\ \ \
+	 * | | | | |
+	 * x 0 1 2 3
+	 *
+	 */
+	const int dashless_parents = 2;
+	int dashful_parents = graph->num_parents - dashless_parents;
+
+	/*
+	 * Usually, each parent gets its own column, like the diagram above, but
+	 * sometimes the first parent goes into an existing column, like this:
+	 *
+	 * | *---.
+	 * | |\ \ \
+	 * |/ / / /
+	 * x 0 1 2
+	 *
+	 * In which case there will be more parents than the delta of columns.
+	 */
+	int delta_cols = (graph->num_new_columns - graph->num_columns);
+	int parent_in_old_cols = graph->num_parents - delta_cols;
+
+	/*
+	 * In both cases, commit_index corresponds to the edge labeled "0".
+	 */
+	int first_col = graph->commit_index + dashless_parents
+	    - parent_in_old_cols;
+
+	int i;
+	for (i = 0; i < dashful_parents; i++) {
+		strbuf_write_column(sb, &graph->new_columns[i+first_col], '-');
+		strbuf_write_column(sb, &graph->new_columns[i+first_col],
+				    i == dashful_parents-1 ? '.' : '-');
 	}
-	col_num = (i / 2) + dashless_commits + graph->commit_index;
-	strbuf_write_column(sb, &graph->new_columns[col_num], '.');
-	return num_dashes + 1;
+	return 2 * dashful_parents;
 }
 
 static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh
new file mode 100755
index 0000000000..dab96c89aa
--- /dev/null
+++ b/t/t4214-log-graph-octopus.sh
@@ -0,0 +1,102 @@
+#!/bin/sh
+
+test_description='git log --graph of skewed left octopus merge.'
+
+. ./test-lib.sh
+
+test_expect_success 'set up merge history' '
+	cat >expect.uncolored <<-\EOF &&
+	* left
+	| *---.   octopus-merge
+	| |\ \ \
+	|/ / / /
+	| | | * 4
+	| | * | 3
+	| | |/
+	| * | 2
+	| |/
+	* | 1
+	|/
+	* initial
+	EOF
+	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> <YELLOW>|<RESET> <BLUE>|<RESET> * 4
+	<RED>|<RESET> <YELLOW>|<RESET> * <MAGENTA>|<RESET> 3
+	<RED>|<RESET> <YELLOW>|<RESET> <MAGENTA>|<RESET><MAGENTA>/<RESET>
+	<RED>|<RESET> * <MAGENTA>|<RESET> 2
+	<RED>|<RESET> <MAGENTA>|<RESET><MAGENTA>/<RESET>
+	* <MAGENTA>|<RESET> 1
+	<MAGENTA>|<RESET><MAGENTA>/<RESET>
+	* initial
+	EOF
+	test_commit initial &&
+	for i in 1 2 3 4 ; do
+		git checkout master -b $i || return $?
+		# Make tag name different from branch name, to avoid
+		# ambiguity error when calling checkout.
+		test_commit $i $i $i tag$i || return $?
+	done &&
+	git checkout 1 -b merge &&
+	test_tick &&
+	git merge -m octopus-merge 1 2 3 4 &&
+	git checkout 1 -b L &&
+	test_commit left
+'
+
+test_expect_success 'log --graph with tricky octopus merge with colors' '
+	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
+	git log --color=always --graph --date-order --pretty=tformat:%s --all >actual.colors.raw &&
+	test_decode_color <actual.colors.raw | sed "s/ *\$//" >actual.colors &&
+	test_cmp expect.colors actual.colors
+'
+
+test_expect_success 'log --graph with tricky octopus merge, no color' '
+	git log --color=never --graph --date-order --pretty=tformat:%s --all >actual.raw &&
+	sed "s/ *\$//" actual.raw >actual &&
+	test_cmp expect.uncolored actual
+'
+
+# Repeat the previous two tests with "normal" octopus merge (i.e.,
+# without the first parent skewing to the "left" branch column).
+
+test_expect_success 'log --graph with normal octopus merge, no color' '
+	cat >expect.uncolored <<-\EOF &&
+	*---.   octopus-merge
+	|\ \ \
+	| | | * 4
+	| | * | 3
+	| | |/
+	| * | 2
+	| |/
+	* | 1
+	|/
+	* initial
+	EOF
+	git log --color=never --graph --date-order --pretty=tformat:%s merge >actual.raw &&
+	sed "s/ *\$//" actual.raw >actual &&
+	test_cmp expect.uncolored actual
+'
+
+test_expect_success 'log --graph with normal octopus merge with colors' '
+	cat >expect.colors <<-\EOF &&
+	*<YELLOW>-<RESET><YELLOW>-<RESET><BLUE>-<RESET><BLUE>.<RESET>   octopus-merge
+	<RED>|<RESET><GREEN>\<RESET> <YELLOW>\<RESET> <BLUE>\<RESET>
+	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET> * 4
+	<RED>|<RESET> <GREEN>|<RESET> * <BLUE>|<RESET> 3
+	<RED>|<RESET> <GREEN>|<RESET> <BLUE>|<RESET><BLUE>/<RESET>
+	<RED>|<RESET> * <BLUE>|<RESET> 2
+	<RED>|<RESET> <BLUE>|<RESET><BLUE>/<RESET>
+	* <BLUE>|<RESET> 1
+	<BLUE>|<RESET><BLUE>/<RESET>
+	* initial
+	EOF
+	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
+	git log --color=always --graph --date-order --pretty=tformat:%s merge >actual.colors.raw &&
+	test_decode_color <actual.colors.raw | sed "s/ *\$//" >actual.colors &&
+	test_cmp expect.colors actual.colors
+'
+test_done
-- 
2.11.0

Re: [PATCH v6] log: fix coloring of certain octupus merge shapes

[Junio C Hamano]

Noam Postavsky <npostavs@users.sourceforge.net> writes:

> For octopus merges where the first parent edge immediately merges into
> the next column to the left:
>
> | *-.
> | |\ \
> |/ / /
>
> then the number of columns should be one less than the usual case:
>
> | *-.
> | |\ \
> | | | *

I had a bit hard time parsing the above, especially with "then",
which probably would make it easier to read if it is not there.

> Also refactor the code to iterate over columns rather than dashes,
> building from an initial patch suggestion by Jeff King.

s/suggestion/suggested/ perhaps?

>
> Signed-off-by: Noam Postavsky <npostavs@users.sourceforge.net>
> Reviewed-by: Jeff King <peff@peff.net>
> ---

Thanks, both.

>  /*
> + * Draw the horizontal dashes of an octopus merge and return the number of
> + * characters written.
>   */
>  static int graph_draw_octopus_merge(struct git_graph *graph,
>  				    struct strbuf *sb)
>  {
>  	/*
> +	 * Here dashless_parents represents the number of parents which don't
> +	 * need to have dashes (the edges labeled "0" and "1").  And
> +	 * dashful_parents are the remaining ones.

Here "dash" refers to that horizontal line on the same line as the
resulting merge.  A very clearly explained definition.  OK.

> +	 * | *---.
> +	 * | |\ \ \
> +	 * | | | | |
> +	 * x 0 1 2 3
> +	 *
> +	 */
> +	const int dashless_parents = 2;

That counts parent #0 (the first parent) and parent #1.

> +	int dashful_parents = graph->num_parents - dashless_parents;

When a mistaken caller calls this function on a commit that is not
an octopus, this can underflow.  dashful_parents would be -1 for a
non-merge, dashful_parents would be 0 for a normal merge, and then
dashful_parents would be 1 for a merge of three histories.  OK.

> +	/*
> +	 * Usually, each parent gets its own column, like the diagram above, but
> +	 * sometimes the first parent goes into an existing column, like this:
> +	 *
> +	 * | *---.
> +	 * | |\ \ \
> +	 * |/ / / /
> +	 * x 0 1 2
> +	 *
> +	 * In which case there will be more parents than the delta of columns.
> +	 */

It is unclear to me what "delta of columns" means here.  Is this
because I am unfamiliar with the internal of graph.[ch] API (and
'delta of columns' is used elsewhere in the API internals already)?

> +	int delta_cols = (graph->num_new_columns - graph->num_columns);

So in the second picture above, new-columns (which is the columns
used after showing the current line) is narrower (because 'x' reuses
an already allocated column without getting a new one) than columns
(which is the columns for the octopus merge we are showing)?

I am not sure I follow what is going on around here, sorry.

> +	int parent_in_old_cols = graph->num_parents - delta_cols;
> +	/*
> +	 * In both cases, commit_index corresponds to the edge labeled "0".
> +	 */
> +	int first_col = graph->commit_index + dashless_parents
> +	    - parent_in_old_cols;
> +
> +	int i;
> +	for (i = 0; i < dashful_parents; i++) {
> +		strbuf_write_column(sb, &graph->new_columns[i+first_col], '-');
> +		strbuf_write_column(sb, &graph->new_columns[i+first_col],
> +				    i == dashful_parents-1 ? '.' : '-');

Draw a dash-dash for each, except we show dash-dot only for the last
one.  OK.  It is interesting that dashful_parents does not have to
change between the two examples you gave above, and it is
understandable because it only depends on the shape of the graph
near the octopus merge itself (in other words, the placement of the
parent commits does not contribute to it at all).  Makes sense.

>  	}
> -	col_num = (i / 2) + dashless_commits + graph->commit_index;
> -	strbuf_write_column(sb, &graph->new_columns[col_num], '.');
> -	return num_dashes + 1;
> +	return 2 * dashful_parents;

This is natural, as we showed either dash-dash or dash-dot only for
dashful_parents after the merge itself. OK.

Thanks, will queue.

Re: [PATCH v6] log: fix coloring of certain octupus merge shapes

[Noam Postavsky]

[-- Attachment #1: Type: text/plain, Size: 2237 bytes --]

On Tue, 9 Oct 2018 at 21:43, Junio C Hamano <gitster@pobox.com> wrote:

> I had a bit hard time parsing the above, especially with "then",
> which probably would make it easier to read if it is not there.

Okay, I guess better to separate the explanation from the diagrams,
rather than weaving them together:

    For octopus merges where the first parent edge immediately merges into
    the next column to the left, the number of columns should be one less
    than the usual case.

    First parent to the left case:

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

    The usual case:

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

> > Also refactor the code to iterate over columns rather than dashes,
> > building from an initial patch suggestion by Jeff King.
>
> s/suggestion/suggested/ perhaps?

Ok.

> It is unclear to me what "delta of columns" means here.  Is this
> because I am unfamiliar with the internal of graph.[ch] API (and
> 'delta of columns' is used elsewhere in the API internals already)?

No, I just meant difference in number of columns from the previous
line to the next. Actually, I had kind of wanted to use "new columns",
but that would be confusing with the num_new_columns variable actually
meaning the total number of columns in the next line.

> > +     int delta_cols = (graph->num_new_columns - graph->num_columns);
>
> So in the second picture above, new-columns (which is the columns
> used after showing the current line) is narrower (because 'x' reuses
> an already allocated column without getting a new one) than columns
> (which is the columns for the octopus merge we are showing)?
>
> I am not sure I follow what is going on around here, sorry.

Maybe it's clearer by saying "added columns" (also expanded the comments a bit)?

    /*
     * Usually, we add one new column for each parent (like the diagram
     * 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
     * number of added columns.
     */
    int added_cols = (graph->num_new_columns - graph->num_columns);
    int parent_in_old_cols = graph->num_parents - added_cols;

[-- Attachment #2: v7-0001-log-fix-coloring-of-certain-octupus-merge-shapes.patch --]
[-- Type: text/x-diff, Size: 6872 bytes --]

From a9c90605c062b30273dad35adbf319905028cacc Mon Sep 17 00:00:00 2001
From: Noam Postavsky <npostavs@users.sourceforge.net>
Date: Sat, 1 Sep 2018 20:07:16 -0400
Subject: [PATCH v7] log: fix coloring of certain octupus merge shapes

For octopus merges where the first parent edge immediately merges into
the next column to the left, the number of columns should be one less
than the usual case.

First parent to the left case:

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

The usual case:

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

Also refactor the code to iterate over columns rather than dashes,
building from an initial patch suggested by Jeff King.

Signed-off-by: Noam Postavsky <npostavs@users.sourceforge.net>
Reviewed-by: Jeff King <peff@peff.net>
---
 graph.c                      |  58 +++++++++++++++++-------
 t/t4214-log-graph-octopus.sh | 102 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 145 insertions(+), 15 deletions(-)
 create mode 100755 t/t4214-log-graph-octopus.sh

diff --git a/graph.c b/graph.c
index e1f6d3bddb..f53135485f 100644
--- a/graph.c
+++ b/graph.c
@@ -842,27 +842,55 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 }
 
 /*
- * Draw an octopus merge and return the number of characters written.
+ * Draw the horizontal dashes of an octopus merge and return the number of
+ * characters written.
  */
 static int graph_draw_octopus_merge(struct git_graph *graph,
 				    struct strbuf *sb)
 {
 	/*
-	 * Here dashless_commits represents the number of parents
-	 * which don't need to have dashes (because their edges fit
-	 * neatly under the commit).
-	 */
-	const int dashless_commits = 2;
-	int col_num, i;
-	int num_dashes =
-		((graph->num_parents - dashless_commits) * 2) - 1;
-	for (i = 0; i < num_dashes; i++) {
-		col_num = (i / 2) + dashless_commits + graph->commit_index;
-		strbuf_write_column(sb, &graph->new_columns[col_num], '-');
+	 * Here dashless_parents represents the number of parents which don't
+	 * need to have dashes (the edges labeled "0" and "1").  And
+	 * dashful_parents are the remaining ones.
+	 *
+	 * | *---.
+	 * | |\ \ \
+	 * | | | | |
+	 * x 0 1 2 3
+	 *
+	 */
+	const int dashless_parents = 2;
+	int dashful_parents = graph->num_parents - dashless_parents;
+
+	/*
+	 * Usually, we add one new column for each parent (like the diagram
+	 * 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
+	 * number of added columns.
+	 */
+	int added_cols = (graph->num_new_columns - graph->num_columns);
+	int parent_in_old_cols = graph->num_parents - added_cols;
+
+	/*
+	 * In both cases, commit_index corresponds to the edge labeled "0".
+	 */
+	int first_col = graph->commit_index + dashless_parents
+	    - parent_in_old_cols;
+
+	int i;
+	for (i = 0; i < dashful_parents; i++) {
+		strbuf_write_column(sb, &graph->new_columns[i+first_col], '-');
+		strbuf_write_column(sb, &graph->new_columns[i+first_col],
+				    i == dashful_parents-1 ? '.' : '-');
 	}
-	col_num = (i / 2) + dashless_commits + graph->commit_index;
-	strbuf_write_column(sb, &graph->new_columns[col_num], '.');
-	return num_dashes + 1;
+	return 2 * dashful_parents;
 }
 
 static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh
new file mode 100755
index 0000000000..dab96c89aa
--- /dev/null
+++ b/t/t4214-log-graph-octopus.sh
@@ -0,0 +1,102 @@
+#!/bin/sh
+
+test_description='git log --graph of skewed left octopus merge.'
+
+. ./test-lib.sh
+
+test_expect_success 'set up merge history' '
+	cat >expect.uncolored <<-\EOF &&
+	* left
+	| *---.   octopus-merge
+	| |\ \ \
+	|/ / / /
+	| | | * 4
+	| | * | 3
+	| | |/
+	| * | 2
+	| |/
+	* | 1
+	|/
+	* initial
+	EOF
+	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> <YELLOW>|<RESET> <BLUE>|<RESET> * 4
+	<RED>|<RESET> <YELLOW>|<RESET> * <MAGENTA>|<RESET> 3
+	<RED>|<RESET> <YELLOW>|<RESET> <MAGENTA>|<RESET><MAGENTA>/<RESET>
+	<RED>|<RESET> * <MAGENTA>|<RESET> 2
+	<RED>|<RESET> <MAGENTA>|<RESET><MAGENTA>/<RESET>
+	* <MAGENTA>|<RESET> 1
+	<MAGENTA>|<RESET><MAGENTA>/<RESET>
+	* initial
+	EOF
+	test_commit initial &&
+	for i in 1 2 3 4 ; do
+		git checkout master -b $i || return $?
+		# Make tag name different from branch name, to avoid
+		# ambiguity error when calling checkout.
+		test_commit $i $i $i tag$i || return $?
+	done &&
+	git checkout 1 -b merge &&
+	test_tick &&
+	git merge -m octopus-merge 1 2 3 4 &&
+	git checkout 1 -b L &&
+	test_commit left
+'
+
+test_expect_success 'log --graph with tricky octopus merge with colors' '
+	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
+	git log --color=always --graph --date-order --pretty=tformat:%s --all >actual.colors.raw &&
+	test_decode_color <actual.colors.raw | sed "s/ *\$//" >actual.colors &&
+	test_cmp expect.colors actual.colors
+'
+
+test_expect_success 'log --graph with tricky octopus merge, no color' '
+	git log --color=never --graph --date-order --pretty=tformat:%s --all >actual.raw &&
+	sed "s/ *\$//" actual.raw >actual &&
+	test_cmp expect.uncolored actual
+'
+
+# Repeat the previous two tests with "normal" octopus merge (i.e.,
+# without the first parent skewing to the "left" branch column).
+
+test_expect_success 'log --graph with normal octopus merge, no color' '
+	cat >expect.uncolored <<-\EOF &&
+	*---.   octopus-merge
+	|\ \ \
+	| | | * 4
+	| | * | 3
+	| | |/
+	| * | 2
+	| |/
+	* | 1
+	|/
+	* initial
+	EOF
+	git log --color=never --graph --date-order --pretty=tformat:%s merge >actual.raw &&
+	sed "s/ *\$//" actual.raw >actual &&
+	test_cmp expect.uncolored actual
+'
+
+test_expect_success 'log --graph with normal octopus merge with colors' '
+	cat >expect.colors <<-\EOF &&
+	*<YELLOW>-<RESET><YELLOW>-<RESET><BLUE>-<RESET><BLUE>.<RESET>   octopus-merge
+	<RED>|<RESET><GREEN>\<RESET> <YELLOW>\<RESET> <BLUE>\<RESET>
+	<RED>|<RESET> <GREEN>|<RESET> <YELLOW>|<RESET> * 4
+	<RED>|<RESET> <GREEN>|<RESET> * <BLUE>|<RESET> 3
+	<RED>|<RESET> <GREEN>|<RESET> <BLUE>|<RESET><BLUE>/<RESET>
+	<RED>|<RESET> * <BLUE>|<RESET> 2
+	<RED>|<RESET> <BLUE>|<RESET><BLUE>/<RESET>
+	* <BLUE>|<RESET> 1
+	<BLUE>|<RESET><BLUE>/<RESET>
+	* initial
+	EOF
+	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
+	git log --color=always --graph --date-order --pretty=tformat:%s merge >actual.colors.raw &&
+	test_decode_color <actual.colors.raw | sed "s/ *\$//" >actual.colors &&
+	test_cmp expect.colors actual.colors
+'
+test_done
-- 
2.11.0

Re: [PATCH v6] log: fix coloring of certain octupus merge shapes

[Junio C Hamano]

I'll do the s/octu/octo/; again on the title while queuing.

Let's merge this to 'next'.

Thanks.