Re: [BUG] A part of an edge from an octopus merge gets colored, even with --color=never

[Jeff King <peff@peff.net>]

On Sat, Jun 23, 2018 at 05:45:19PM -0400, Noam Postavsky wrote:

> On 20 May 2016 at 18:12, Noam Postavsky <npostavs@users.sourceforge.net> wrote:

My, this is a blast from the past. :)

> Subject: [PATCH v1] 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:
> 
> | | *-.
> | | |\ \
> | |/ / /
> 
> then the number of columns should be one less than the usual case:
> 
> | *-.
> | |\ \
> | | | *

These diagrams confused me for a minute, because I see two differences:

  1. The first one has an extra apparently unrelated parallel branch on
     the far left.

  2. The first has the first-parent of the "*" merge commit immediately
     join the branch.

But if I understand correctly, we only care about the second property.
So would it be accurate to show them as:

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

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

?

I think that makes it easier to compare them.

I don't remember much about our prior discussion, so let me try to talk
myself through the patch itself:

> diff --git a/graph.c b/graph.c
> index e1f6d3bdd..c919c86e8 100644
> --- a/graph.c
> +++ b/graph.c
> @@ -856,12 +856,16 @@ static int graph_draw_octopus_merge(struct git_graph *graph,
>  	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;

OK, so the old code emitted num_dashes, and every pair was done with the
same column. Our highest iteration of this loop would use the column at
(num_dashes-1) / 2. We know that num_dashes is always odd, so:

 num_dashes = 1 puts our last column at 0
 num_dashes = 3 puts our last column at 1

And so on. So far so good.

> +	int first_col = dashless_commits + graph->commit_index;

This corresponds to the i=0 case, makes sense.

> +	int last_col = first_col + (num_dashes / 2);

But here our last_col misses the "-1". I don't think it matters because
we know num_dashes is always odd, and therefore due to integer
truncation (num_dashes-1)/2 == (num_dashes/2).

> +	if (last_col >= graph->num_new_columns) {
> +		first_col--;
> +		last_col--;
> +	}

The shifting of last_col I expect as part of the fix. I was surprised by
shifting first_col, though. Wouldn't it always start at 0 (offset by the
previous commits)? It definitely seems to be necessary, but I'm not sure
I understand why.

> +	for (i = 0, col_num = first_col; i < num_dashes; i++, col_num++) {
>  		strbuf_write_column(sb, &graph->new_columns[col_num], '-');
>  	}
> -	col_num = (i / 2) + dashless_commits + graph->commit_index;
> -	strbuf_write_column(sb, &graph->new_columns[col_num], '.');
> +	strbuf_write_column(sb, &graph->new_columns[last_col], '.');

In this new loop we count up our dashes and our columns. But now we have
1-to-1 correspondence as we increment! I don't think that can be right.
And indeed, if I take your original problem report and add an extra "d"
branch and make the octopus "a b d", then the problem comes back. You
don't notice with a 3-parent merge because 

We need to increment col_num only half as much as num_dashes. Should we
be doing:

  for (col_num = first_col; col_num < last_col; col_num++) {
	  strbuf_write_column(sb, &graph->new_columns[col_num], '-');
	  strbuf_write_column(sb, &graph->new_columns[col_num], '-');
  }
  strbuf_write_column(sb, &graph->new_columns[last_col], '-');
  strbuf_write_column(sb, &graph->new_columns[last_col], '.');

I.e., write "--" for each interior column, and then "-." for the last
one?

-Peff