[01/11] graph: automatically track visible width of `strbuf`

Commit Message

John Cai via GitGitGadget Oct. 10, 2019, 4:13 p.m. UTC

From: James Coglan <[e-mail]>

All the output functions in `graph.c` currently keep track of how many
printable chars they've written to the buffer, before calling
`graph_pad_horizontally()` to pad the line with spaces. Some functions
do this by incrementing a counter whenever they write to the buffer, and
others do it by encoding an assumption about how many chars are written,
as in:

    graph_pad_horizontally(graph, sb, graph->num_columns * 2);

This adds a fair amount of noise to the functions' logic and is easily
broken if one forgets to increment the right counter or update the
calculations used for padding.

To make this easier to use, I'm adding a `width` field to `strbuf` that
tracks the number of printing characters added after the line prefix.
It's set to 0 at the start of `graph_next_line()`, and then various
`strbuf` functions update it as follows:

- `strbuf_write_column()` increments `width` by 1

- `strbuf_setlen()` changes `width` by the amount added to `len` if
  `len` is increased, or makes `width` and `len` the same if it's
  decreased

- `strbuf_addch()` increments `width` by 1

This is enough to ensure that the functions used by `graph.c` update
`strbuf->width` correctly, and `graph_pad_horizontally()` can then use
this field instead of taking `chars_written` as a parameter.

Signed-off-by: James Coglan <[e-mail]>
---
 graph.c  | 68 ++++++++++++++++++++++----------------------------------
 strbuf.h |  8 ++++++-
 2 files changed, 33 insertions(+), 43 deletions(-)

Comments

Johannes Schindelin Oct. 10, 2019, 9:07 p.m. UTC | #1

Hi James,

On Thu, 10 Oct 2019, James Coglan via GitGitGadget wrote:

> From: James Coglan <[e-mail]>
>
> All the output functions in `graph.c` currently keep track of how many
> printable chars they've written to the buffer, before calling
> `graph_pad_horizontally()` to pad the line with spaces. Some functions
> do this by incrementing a counter whenever they write to the buffer, and
> others do it by encoding an assumption about how many chars are written,
> as in:
>
>     graph_pad_horizontally(graph, sb, graph->num_columns * 2);
>
> This adds a fair amount of noise to the functions' logic and is easily
> broken if one forgets to increment the right counter or update the
> calculations used for padding.
>
> To make this easier to use, I'm adding a `width` field to `strbuf` that
> tracks the number of printing characters added after the line prefix.

This is a big heavy-handed: adding a `width` field to `struct strbuf`
and maintaining it _just_ for the purpose of `graph.c` puts an
unnecssary load on every other `strbuf` user (of which there are a
_lot_).

So my obvious question is: what makes `width` different from `len`?
Since we exclusively use ASCII characters for the graph part, we should
be able to use the already-existing `len`, for free, no?

I could imagine that the `strbuf` might receive more than one line, but
then we still would only need to remember the offset of the last newline
character in that `strbuf`, no?

Ciao,
Johannes

> It's set to 0 at the start of `graph_next_line()`, and then various
> `strbuf` functions update it as follows:
>
> - `strbuf_write_column()` increments `width` by 1
>
> - `strbuf_setlen()` changes `width` by the amount added to `len` if
>   `len` is increased, or makes `width` and `len` the same if it's
>   decreased
>
> - `strbuf_addch()` increments `width` by 1
>
> This is enough to ensure that the functions used by `graph.c` update
> `strbuf->width` correctly, and `graph_pad_horizontally()` can then use
> this field instead of taking `chars_written` as a parameter.
>
> Signed-off-by: James Coglan <[e-mail]>
> ---
>  graph.c  | 68 ++++++++++++++++++++++----------------------------------
>  strbuf.h |  8 ++++++-
>  2 files changed, 33 insertions(+), 43 deletions(-)
>
> diff --git a/graph.c b/graph.c
> index f53135485f..c56fdec1fc 100644
> --- a/graph.c
> +++ b/graph.c
> @@ -115,11 +115,20 @@ static const char *column_get_color_code(unsigned short color)
>  static void strbuf_write_column(struct strbuf *sb, const struct column *c,
>  				char col_char)
>  {
> +	/*
> +	 * Remember the buffer's width as we're about to add non-printing
> +	 * content to it, and we want to avoid counting the byte length
> +	 * of this content towards the buffer's visible width
> +	 */
> +	size_t prev_width = sb->width;
> +
>  	if (c->color < column_colors_max)
>  		strbuf_addstr(sb, column_get_color_code(c->color));
>  	strbuf_addch(sb, col_char);
>  	if (c->color < column_colors_max)
>  		strbuf_addstr(sb, column_get_color_code(column_colors_max));
> +
> +	sb->width = prev_width + 1;
>  }
>
>  struct git_graph {
> @@ -686,8 +695,7 @@ static int graph_is_mapping_correct(struct git_graph *graph)
>  	return 1;
>  }
>
> -static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
> -				   int chars_written)
> +static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)
>  {
>  	/*
>  	 * Add additional spaces to the end of the strbuf, so that all
> @@ -696,8 +704,8 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
>  	 * This way, fields printed to the right of the graph will remain
>  	 * aligned for the entire commit.
>  	 */
> -	if (chars_written < graph->width)
> -		strbuf_addchars(sb, ' ', graph->width - chars_written);
> +	if (sb->width < graph->width)
> +		strbuf_addchars(sb, ' ', graph->width - sb->width);
>  }
>
>  static void graph_output_padding_line(struct git_graph *graph,
> @@ -723,7 +731,7 @@ static void graph_output_padding_line(struct git_graph *graph,
>  		strbuf_addch(sb, ' ');
>  	}
>
> -	graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
> +	graph_pad_horizontally(graph, sb);
>  }
>
>
> @@ -740,7 +748,7 @@ static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
>  	 * of the graph is missing.
>  	 */
>  	strbuf_addstr(sb, "...");
> -	graph_pad_horizontally(graph, sb, 3);
> +	graph_pad_horizontally(graph, sb);
>
>  	if (graph->num_parents >= 3 &&
>  	    graph->commit_index < (graph->num_columns - 1))
> @@ -754,7 +762,6 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>  {
>  	int num_expansion_rows;
>  	int i, seen_this;
> -	int chars_written;
>
>  	/*
>  	 * This function formats a row that increases the space around a commit
> @@ -777,14 +784,12 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>  	 * Output the row
>  	 */
>  	seen_this = 0;
> -	chars_written = 0;
>  	for (i = 0; i < graph->num_columns; i++) {
>  		struct column *col = &graph->columns[i];
>  		if (col->commit == graph->commit) {
>  			seen_this = 1;
>  			strbuf_write_column(sb, col, '|');
>  			strbuf_addchars(sb, ' ', graph->expansion_row);
> -			chars_written += 1 + graph->expansion_row;
>  		} else if (seen_this && (graph->expansion_row == 0)) {
>  			/*
>  			 * This is the first line of the pre-commit output.
> @@ -800,19 +805,15 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>  				strbuf_write_column(sb, col, '\\');
>  			else
>  				strbuf_write_column(sb, col, '|');
> -			chars_written++;
>  		} else if (seen_this && (graph->expansion_row > 0)) {
>  			strbuf_write_column(sb, col, '\\');
> -			chars_written++;
>  		} else {
>  			strbuf_write_column(sb, col, '|');
> -			chars_written++;
>  		}
>  		strbuf_addch(sb, ' ');
> -		chars_written++;
>  	}
>
> -	graph_pad_horizontally(graph, sb, chars_written);
> +	graph_pad_horizontally(graph, sb);
>
>  	/*
>  	 * Increment graph->expansion_row,
> @@ -842,11 +843,9 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
>  }
>
>  /*
> - * Draw the horizontal dashes of an octopus merge and return the number of
> - * characters written.
> + * Draw the horizontal dashes of an octopus merge.
>   */
> -static int graph_draw_octopus_merge(struct git_graph *graph,
> -				    struct strbuf *sb)
> +static void graph_draw_octopus_merge(struct git_graph *graph, struct strbuf *sb)
>  {
>  	/*
>  	 * Here dashless_parents represents the number of parents which don't
> @@ -890,13 +889,12 @@ static int graph_draw_octopus_merge(struct git_graph *graph,
>  		strbuf_write_column(sb, &graph->new_columns[i+first_col],
>  				    i == dashful_parents-1 ? '.' : '-');
>  	}
> -	return 2 * dashful_parents;
>  }
>
>  static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  {
>  	int seen_this = 0;
> -	int i, chars_written;
> +	int i;
>
>  	/*
>  	 * Output the row containing this commit
> @@ -906,7 +904,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  	 * children that we have already processed.)
>  	 */
>  	seen_this = 0;
> -	chars_written = 0;
>  	for (i = 0; i <= graph->num_columns; i++) {
>  		struct column *col = &graph->columns[i];
>  		struct commit *col_commit;
> @@ -921,14 +918,11 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  		if (col_commit == graph->commit) {
>  			seen_this = 1;
>  			graph_output_commit_char(graph, sb);
> -			chars_written++;
>
>  			if (graph->num_parents > 2)
> -				chars_written += graph_draw_octopus_merge(graph,
> -									  sb);
> +				graph_draw_octopus_merge(graph, sb);
>  		} else if (seen_this && (graph->num_parents > 2)) {
>  			strbuf_write_column(sb, col, '\\');
> -			chars_written++;
>  		} else if (seen_this && (graph->num_parents == 2)) {
>  			/*
>  			 * This is a 2-way merge commit.
> @@ -948,16 +942,13 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  				strbuf_write_column(sb, col, '\\');
>  			else
>  				strbuf_write_column(sb, col, '|');
> -			chars_written++;
>  		} else {
>  			strbuf_write_column(sb, col, '|');
> -			chars_written++;
>  		}
>  		strbuf_addch(sb, ' ');
> -		chars_written++;
>  	}
>
> -	graph_pad_horizontally(graph, sb, chars_written);
> +	graph_pad_horizontally(graph, sb);
>
>  	/*
>  	 * Update graph->state
> @@ -984,12 +975,11 @@ static struct column *find_new_column_by_commit(struct git_graph *graph,
>  static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
>  {
>  	int seen_this = 0;
> -	int i, j, chars_written;
> +	int i, j;
>
>  	/*
>  	 * Output the post-merge row
>  	 */
> -	chars_written = 0;
>  	for (i = 0; i <= graph->num_columns; i++) {
>  		struct column *col = &graph->columns[i];
>  		struct commit *col_commit;
> @@ -1017,7 +1007,6 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
>  			assert(par_column);
>
>  			strbuf_write_column(sb, par_column, '|');
> -			chars_written++;
>  			for (j = 0; j < graph->num_parents - 1; j++) {
>  				parents = next_interesting_parent(graph, parents);
>  				assert(parents);
> @@ -1026,19 +1015,16 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
>  				strbuf_write_column(sb, par_column, '\\');
>  				strbuf_addch(sb, ' ');
>  			}
> -			chars_written += j * 2;
>  		} else if (seen_this) {
>  			strbuf_write_column(sb, col, '\\');
>  			strbuf_addch(sb, ' ');
> -			chars_written += 2;
>  		} else {
>  			strbuf_write_column(sb, col, '|');
>  			strbuf_addch(sb, ' ');
> -			chars_written += 2;
>  		}
>  	}
>
> -	graph_pad_horizontally(graph, sb, chars_written);
> +	graph_pad_horizontally(graph, sb);
>
>  	/*
>  	 * Update graph->state
> @@ -1181,7 +1167,7 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
>  		}
>  	}
>
> -	graph_pad_horizontally(graph, sb, graph->mapping_size);
> +	graph_pad_horizontally(graph, sb);
>
>  	/*
>  	 * Swap mapping and new_mapping
> @@ -1199,6 +1185,8 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
>
>  int graph_next_line(struct git_graph *graph, struct strbuf *sb)
>  {
> +	sb->width = 0;
> +
>  	switch (graph->state) {
>  	case GRAPH_PADDING:
>  		graph_output_padding_line(graph, sb);
> @@ -1227,7 +1215,6 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb)
>  static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
>  {
>  	int i;
> -	int chars_written = 0;
>
>  	if (graph->state != GRAPH_COMMIT) {
>  		graph_next_line(graph, sb);
> @@ -1245,19 +1232,16 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
>  		struct column *col = &graph->columns[i];
>
>  		strbuf_write_column(sb, col, '|');
> -		chars_written++;
>
>  		if (col->commit == graph->commit && graph->num_parents > 2) {
>  			int len = (graph->num_parents - 2) * 2;
>  			strbuf_addchars(sb, ' ', len);
> -			chars_written += len;
>  		} else {
>  			strbuf_addch(sb, ' ');
> -			chars_written++;
>  		}
>  	}
>
> -	graph_pad_horizontally(graph, sb, chars_written);
> +	graph_pad_horizontally(graph, sb);
>
>  	/*
>  	 * Update graph->prev_state since we have output a padding line
> diff --git a/strbuf.h b/strbuf.h
> index f62278a0be..3a98147321 100644
> --- a/strbuf.h
> +++ b/strbuf.h
> @@ -66,11 +66,12 @@ struct string_list;
>  struct strbuf {
>  	size_t alloc;
>  	size_t len;
> +	size_t width;
>  	char *buf;
>  };
>
>  extern char strbuf_slopbuf[];
> -#define STRBUF_INIT  { .alloc = 0, .len = 0, .buf = strbuf_slopbuf }
> +#define STRBUF_INIT  { .alloc = 0, .len = 0, .width = 0, .buf = strbuf_slopbuf }
>
>  /*
>   * Predeclare this here, since cache.h includes this file before it defines the
> @@ -161,6 +162,10 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
>  {
>  	if (len > (sb->alloc ? sb->alloc - 1 : 0))
>  		die("BUG: strbuf_setlen() beyond buffer");
> +	if (len > sb->len)
> +		sb->width += len - sb->len;
> +	else
> +		sb->width = len;
>  	sb->len = len;
>  	if (sb->buf != strbuf_slopbuf)
>  		sb->buf[len] = '\0';
> @@ -231,6 +236,7 @@ static inline void strbuf_addch(struct strbuf *sb, int c)
>  		strbuf_grow(sb, 1);
>  	sb->buf[sb->len++] = c;
>  	sb->buf[sb->len] = '\0';
> +	sb->width++;
>  }
>
>  /**
> --
> gitgitgadget
>
>

Denton Liu Oct. 10, 2019, 11:05 p.m. UTC | #2

Hi Dscho,

On Thu, Oct 10, 2019 at 11:07:35PM +0200, Johannes Schindelin wrote:
> Hi James,
> 
> On Thu, 10 Oct 2019, James Coglan via GitGitGadget wrote:
> 
> > From: James Coglan <[e-mail]>
> >
> > All the output functions in `graph.c` currently keep track of how many
> > printable chars they've written to the buffer, before calling
> > `graph_pad_horizontally()` to pad the line with spaces. Some functions
> > do this by incrementing a counter whenever they write to the buffer, and
> > others do it by encoding an assumption about how many chars are written,
> > as in:
> >
> >     graph_pad_horizontally(graph, sb, graph->num_columns * 2);
> >
> > This adds a fair amount of noise to the functions' logic and is easily
> > broken if one forgets to increment the right counter or update the
> > calculations used for padding.
> >
> > To make this easier to use, I'm adding a `width` field to `strbuf` that
> > tracks the number of printing characters added after the line prefix.
> 
> This is a big heavy-handed: adding a `width` field to `struct strbuf`
> and maintaining it _just_ for the purpose of `graph.c` puts an
> unnecssary load on every other `strbuf` user (of which there are a
> _lot_).
> 
> So my obvious question is: what makes `width` different from `len`?
> Since we exclusively use ASCII characters for the graph part, we should
> be able to use the already-existing `len`, for free, no?

From what I can gleam from looking at the code, `width` is different
from `len` because when we're printing with colours, there'll be a bunch
of termcodes that don't actually count for the width.

I think that we should either leave the `chars_written` variable as is
or maybe calculate it after the fact. Here's an untested and uncompiled
implementation of something that might do that:

	static int calculate_width(const struct strbuf *row)
	{
		int in_termcode = 0;
		int width = 0;
		int i;

		for (i = 0; i < row.len; i++) {
			if (row.buf[i] == '\033')
				in_termcode = 1;

			if (!in_termcode)
				width++;
			else if (row.buf[i] == 'm')
				in_termcode = 0;
		}
	}

If we include this, I'm not sure what kind of performance hit we might
take if the graph we're generating is particularly big, though.

> 
> I could imagine that the `strbuf` might receive more than one line, but
> then we still would only need to remember the offset of the last newline
> character in that `strbuf`, no?
> 
> Ciao,
> Johannes

Derrick Stolee Oct. 11, 2019, 12:49 a.m. UTC | #3

On 10/10/2019 7:05 PM, Denton Liu wrote:
> Hi Dscho,
> 
> On Thu, Oct 10, 2019 at 11:07:35PM +0200, Johannes Schindelin wrote:
>> Hi James,
>>
>> On Thu, 10 Oct 2019, James Coglan via GitGitGadget wrote:
>>
>>> From: James Coglan <[e-mail]>
>>>
>>> All the output functions in `graph.c` currently keep track of how many
>>> printable chars they've written to the buffer, before calling
>>> `graph_pad_horizontally()` to pad the line with spaces. Some functions
>>> do this by incrementing a counter whenever they write to the buffer, and
>>> others do it by encoding an assumption about how many chars are written,
>>> as in:
>>>
>>>     graph_pad_horizontally(graph, sb, graph->num_columns * 2);
>>>
>>> This adds a fair amount of noise to the functions' logic and is easily
>>> broken if one forgets to increment the right counter or update the
>>> calculations used for padding.
>>>
>>> To make this easier to use, I'm adding a `width` field to `strbuf` that
>>> tracks the number of printing characters added after the line prefix.
>>
>> This is a big heavy-handed: adding a `width` field to `struct strbuf`
>> and maintaining it _just_ for the purpose of `graph.c` puts an
>> unnecssary load on every other `strbuf` user (of which there are a
>> _lot_).

I was concerned about this, too.

>> So my obvious question is: what makes `width` different from `len`?
>> Since we exclusively use ASCII characters for the graph part, we should
>> be able to use the already-existing `len`, for free, no?
> 
> From what I can gleam from looking at the code, `width` is different
> from `len` because when we're printing with colours, there'll be a bunch
> of termcodes that don't actually count for the width.
> 
> I think that we should either leave the `chars_written` variable as is
> or maybe calculate it after the fact. Here's an untested and uncompiled
> implementation of something that might do that:
> 
> 	static int calculate_width(const struct strbuf *row)
> 	{
> 		int in_termcode = 0;
> 		int width = 0;
> 		int i;
> 
> 		for (i = 0; i < row.len; i++) {
> 			if (row.buf[i] == '\033')
> 				in_termcode = 1;
> 
> 			if (!in_termcode)
> 				width++;
> 			else if (row.buf[i] == 'm')
> 				in_termcode = 0;
> 		}
> 	}
> 
> If we include this, I'm not sure what kind of performance hit we might
> take if the graph we're generating is particularly big, though.

This is worth trying. In terms of CPU time, this should be a mere
blip compared to all of the commit walking that is going on. (Unless
we get to thousands of columns, but by then the output is useless.)

Of course, we should measure the impact, but it is worth a try.

-Stolee

Junio C Hamano Oct. 11, 2019, 1:40 a.m. UTC | #4

Johannes Schindelin <[e-mail]> writes:

> This is a big heavy-handed: adding a `width` field to `struct strbuf`
> and maintaining it _just_ for the purpose of `graph.c` puts an
> unnecssary load on every other `strbuf` user (of which there are a
> _lot_).
>
> So my obvious question is: what makes `width` different from `len`?
> Since we exclusively use ASCII characters for the graph part, we should
> be able to use the already-existing `len`, for free, no?

A red-colored piece on the line consumes <RED><RESET> bytes more
than the payload.  Which is counted as part of "len".  These bytes
do not consume any display width.

When the payload is a basic CJK char in UTF-8 it may typically use 3
byte, while consuming only two display columns.

So I can understand that this application may want to keep track of
<byte sequence, byte sequence length, display width> tuple.

I also understand that a programmer inexperienced/unfamiliar with
our codebase may find it an easy way to satisfiy the need to add an
extra field to strbuf.  But as you pointed out, that is a hack
unacceptable in the larger picture.  Use of strbuf as "auto resizing
byte array, represented as a <byte sequence, byte sequence length>
tuple" is everywhere and we do not want to bloat it.

Thanks for spotting and raising this unfortunate show-stopper issue.
The problem being solved is worth solving, but it needs to be done
without butchering a basic data structure used elsewhere.

Junio C Hamano Oct. 11, 2019, 1:42 a.m. UTC | #5

Denton Liu <[e-mail]> writes:

> 	static int calculate_width(const struct strbuf *row)
> 	{
> 		int in_termcode = 0;
> 		int width = 0;
> 		int i;
>
> 		for (i = 0; i < row.len; i++) {
> 			if (row.buf[i] == '\033')
> 				in_termcode = 1;
>
> 			if (!in_termcode)
> 				width++;
> 			else if (row.buf[i] == 'm')
> 				in_termcode = 0;
> 		}
> 	}

Not every byte that is outside the escape sequence contributes to
one display columns.  You would want to take a look at utf8_width()
for inspiration.

Denton Liu Oct. 11, 2019, 5:01 a.m. UTC | #6

On Fri, Oct 11, 2019 at 10:42:20AM +0900, Junio C Hamano wrote:
> Denton Liu <[e-mail]> writes:
> 
> > 	static int calculate_width(const struct strbuf *row)
> > 	{
> > 		int in_termcode = 0;
> > 		int width = 0;
> > 		int i;
> >
> > 		for (i = 0; i < row.len; i++) {
> > 			if (row.buf[i] == '\033')
> > 				in_termcode = 1;
> >
> > 			if (!in_termcode)
> > 				width++;
> > 			else if (row.buf[i] == 'm')
> > 				in_termcode = 0;
> > 		}
> > 	}
> 
> Not every byte that is outside the escape sequence contributes to
> one display columns.  You would want to take a look at utf8_width()
> for inspiration.
> 

Heh, I guess you're right. Looking right below the definition of
utf8_width, I realised we have the utf8_strnwidth function. We should be
able to just call

	utf8_strnwidth(row.buf, row.len, 1);

Johannes Schindelin Oct. 11, 2019, 4:02 p.m. UTC | #7

Hi,

On Thu, 10 Oct 2019, Denton Liu wrote:

> On Fri, Oct 11, 2019 at 10:42:20AM +0900, Junio C Hamano wrote:
> > Denton Liu <[e-mail]> writes:
> >
> > > 	static int calculate_width(const struct strbuf *row)
> > > 	{
> > > 		int in_termcode = 0;
> > > 		int width = 0;
> > > 		int i;
> > >
> > > 		for (i = 0; i < row.len; i++) {
> > > 			if (row.buf[i] == '\033')
> > > 				in_termcode = 1;
> > >
> > > 			if (!in_termcode)
> > > 				width++;
> > > 			else if (row.buf[i] == 'm')
> > > 				in_termcode = 0;
> > > 		}
> > > 	}
> >
> > Not every byte that is outside the escape sequence contributes to
> > one display columns.  You would want to take a look at utf8_width()
> > for inspiration.
> >
>
> Heh, I guess you're right. Looking right below the definition of
> utf8_width, I realised we have the utf8_strnwidth function. We should be
> able to just call
>
> 	utf8_strnwidth(row.buf, row.len, 1);

Correct me if I'm wrong, but don't we want to keep track of the columns
*only* in the part with the actual line graph, i.e. we're not at all
interested in the onelines' widths?

If so, I could imagine that a good idea would be to introduce

	struct graphbuf {
		struct strbuf buf;
		int width;
	};

and then introduce wrappers for `_addch()` and whatever else is used in
`graph.c`, these wrappers will increment the width together with the
`buf.len` field, and one additional helper that adds color sequences to
that graphbuf that leaves `width` unchanged.

Ciao,
Dscho

James Coglan Oct. 11, 2019, 5:08 p.m. UTC | #8

Hi Johannes,

On 10/10/2019 22:07, Johannes Schindelin wrote:
> Hi James,
> 
> On Thu, 10 Oct 2019, James Coglan via GitGitGadget wrote:
> 
>> From: James Coglan <[e-mail]>
>>
>> All the output functions in `graph.c` currently keep track of how many
>> printable chars they've written to the buffer, before calling
>> `graph_pad_horizontally()` to pad the line with spaces. Some functions
>> do this by incrementing a counter whenever they write to the buffer, and
>> others do it by encoding an assumption about how many chars are written,
>> as in:
>>
>>     graph_pad_horizontally(graph, sb, graph->num_columns * 2);
>>
>> This adds a fair amount of noise to the functions' logic and is easily
>> broken if one forgets to increment the right counter or update the
>> calculations used for padding.
>>
>> To make this easier to use, I'm adding a `width` field to `strbuf` that
>> tracks the number of printing characters added after the line prefix.
> 
> This is a big heavy-handed: adding a `width` field to `struct strbuf`
> and maintaining it _just_ for the purpose of `graph.c` puts an
> unnecssary load on every other `strbuf` user (of which there are a
> _lot_).

I was anticipating there might be objections to modifying a widely used struct. There are other idea I had for solving this that I can share -- I'll post an alternative to this patch shortly that does not involve changing `strbuf`.
 
> So my obvious question is: what makes `width` different from `len`?
> Since we exclusively use ASCII characters for the graph part, we should
> be able to use the already-existing `len`, for free, no?

`len` counts the number of bytes in the buffer, which may include non-printing bytes used to apply color formatting. For padding graph lines, we need to know the number of display columns the buffer will use, and that's what `width` was added for.

> I could imagine that the `strbuf` might receive more than one line, but
> then we still would only need to remember the offset of the last newline
> character in that `strbuf`, no?

As far as I know, it does not contain multiple lines when used in graph.c, but I agree the implementation I've submitted here is obviously wrong if you wanted to use it to get the width of multi-line text. Putting code in strbuf that only works in graph.c and not more broadly was probably a mistake on my part.
> 
>> It's set to 0 at the start of `graph_next_line()`, and then various
>> `strbuf` functions update it as follows:
>>
>> - `strbuf_write_column()` increments `width` by 1
>>
>> - `strbuf_setlen()` changes `width` by the amount added to `len` if
>>   `len` is increased, or makes `width` and `len` the same if it's
>>   decreased
>>
>> - `strbuf_addch()` increments `width` by 1
>>
>> This is enough to ensure that the functions used by `graph.c` update
>> `strbuf->width` correctly, and `graph_pad_horizontally()` can then use
>> this field instead of taking `chars_written` as a parameter.
>>
>> Signed-off-by: James Coglan <[e-mail]>
>> ---
>>  graph.c  | 68 ++++++++++++++++++++++----------------------------------
>>  strbuf.h |  8 ++++++-
>>  2 files changed, 33 insertions(+), 43 deletions(-)
>>
>> diff --git a/graph.c b/graph.c
>> index f53135485f..c56fdec1fc 100644
>> --- a/graph.c
>> +++ b/graph.c
>> @@ -115,11 +115,20 @@ static const char *column_get_color_code(unsigned short color)
>>  static void strbuf_write_column(struct strbuf *sb, const struct column *c,
>>  				char col_char)
>>  {
>> +	/*
>> +	 * Remember the buffer's width as we're about to add non-printing
>> +	 * content to it, and we want to avoid counting the byte length
>> +	 * of this content towards the buffer's visible width
>> +	 */
>> +	size_t prev_width = sb->width;
>> +
>>  	if (c->color < column_colors_max)
>>  		strbuf_addstr(sb, column_get_color_code(c->color));
>>  	strbuf_addch(sb, col_char);
>>  	if (c->color < column_colors_max)
>>  		strbuf_addstr(sb, column_get_color_code(column_colors_max));
>> +
>> +	sb->width = prev_width + 1;
>>  }
>>
>>  struct git_graph {
>> @@ -686,8 +695,7 @@ static int graph_is_mapping_correct(struct git_graph *graph)
>>  	return 1;
>>  }
>>
>> -static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
>> -				   int chars_written)
>> +static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)
>>  {
>>  	/*
>>  	 * Add additional spaces to the end of the strbuf, so that all
>> @@ -696,8 +704,8 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
>>  	 * This way, fields printed to the right of the graph will remain
>>  	 * aligned for the entire commit.
>>  	 */
>> -	if (chars_written < graph->width)
>> -		strbuf_addchars(sb, ' ', graph->width - chars_written);
>> +	if (sb->width < graph->width)
>> +		strbuf_addchars(sb, ' ', graph->width - sb->width);
>>  }
>>
>>  static void graph_output_padding_line(struct git_graph *graph,
>> @@ -723,7 +731,7 @@ static void graph_output_padding_line(struct git_graph *graph,
>>  		strbuf_addch(sb, ' ');
>>  	}
>>
>> -	graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
>> +	graph_pad_horizontally(graph, sb);
>>  }
>>
>>
>> @@ -740,7 +748,7 @@ static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
>>  	 * of the graph is missing.
>>  	 */
>>  	strbuf_addstr(sb, "...");
>> -	graph_pad_horizontally(graph, sb, 3);
>> +	graph_pad_horizontally(graph, sb);
>>
>>  	if (graph->num_parents >= 3 &&
>>  	    graph->commit_index < (graph->num_columns - 1))
>> @@ -754,7 +762,6 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>>  {
>>  	int num_expansion_rows;
>>  	int i, seen_this;
>> -	int chars_written;
>>
>>  	/*
>>  	 * This function formats a row that increases the space around a commit
>> @@ -777,14 +784,12 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>>  	 * Output the row
>>  	 */
>>  	seen_this = 0;
>> -	chars_written = 0;
>>  	for (i = 0; i < graph->num_columns; i++) {
>>  		struct column *col = &graph->columns[i];
>>  		if (col->commit == graph->commit) {
>>  			seen_this = 1;
>>  			strbuf_write_column(sb, col, '|');
>>  			strbuf_addchars(sb, ' ', graph->expansion_row);
>> -			chars_written += 1 + graph->expansion_row;
>>  		} else if (seen_this && (graph->expansion_row == 0)) {
>>  			/*
>>  			 * This is the first line of the pre-commit output.
>> @@ -800,19 +805,15 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>>  				strbuf_write_column(sb, col, '\\');
>>  			else
>>  				strbuf_write_column(sb, col, '|');
>> -			chars_written++;
>>  		} else if (seen_this && (graph->expansion_row > 0)) {
>>  			strbuf_write_column(sb, col, '\\');
>> -			chars_written++;
>>  		} else {
>>  			strbuf_write_column(sb, col, '|');
>> -			chars_written++;
>>  		}
>>  		strbuf_addch(sb, ' ');
>> -		chars_written++;
>>  	}
>>
>> -	graph_pad_horizontally(graph, sb, chars_written);
>> +	graph_pad_horizontally(graph, sb);
>>
>>  	/*
>>  	 * Increment graph->expansion_row,
>> @@ -842,11 +843,9 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
>>  }
>>
>>  /*
>> - * Draw the horizontal dashes of an octopus merge and return the number of
>> - * characters written.
>> + * Draw the horizontal dashes of an octopus merge.
>>   */
>> -static int graph_draw_octopus_merge(struct git_graph *graph,
>> -				    struct strbuf *sb)
>> +static void graph_draw_octopus_merge(struct git_graph *graph, struct strbuf *sb)
>>  {
>>  	/*
>>  	 * Here dashless_parents represents the number of parents which don't
>> @@ -890,13 +889,12 @@ static int graph_draw_octopus_merge(struct git_graph *graph,
>>  		strbuf_write_column(sb, &graph->new_columns[i+first_col],
>>  				    i == dashful_parents-1 ? '.' : '-');
>>  	}
>> -	return 2 * dashful_parents;
>>  }
>>
>>  static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>>  {
>>  	int seen_this = 0;
>> -	int i, chars_written;
>> +	int i;
>>
>>  	/*
>>  	 * Output the row containing this commit
>> @@ -906,7 +904,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>>  	 * children that we have already processed.)
>>  	 */
>>  	seen_this = 0;
>> -	chars_written = 0;
>>  	for (i = 0; i <= graph->num_columns; i++) {
>>  		struct column *col = &graph->columns[i];
>>  		struct commit *col_commit;
>> @@ -921,14 +918,11 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>>  		if (col_commit == graph->commit) {
>>  			seen_this = 1;
>>  			graph_output_commit_char(graph, sb);
>> -			chars_written++;
>>
>>  			if (graph->num_parents > 2)
>> -				chars_written += graph_draw_octopus_merge(graph,
>> -									  sb);
>> +				graph_draw_octopus_merge(graph, sb);
>>  		} else if (seen_this && (graph->num_parents > 2)) {
>>  			strbuf_write_column(sb, col, '\\');
>> -			chars_written++;
>>  		} else if (seen_this && (graph->num_parents == 2)) {
>>  			/*
>>  			 * This is a 2-way merge commit.
>> @@ -948,16 +942,13 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>>  				strbuf_write_column(sb, col, '\\');
>>  			else
>>  				strbuf_write_column(sb, col, '|');
>> -			chars_written++;
>>  		} else {
>>  			strbuf_write_column(sb, col, '|');
>> -			chars_written++;
>>  		}
>>  		strbuf_addch(sb, ' ');
>> -		chars_written++;
>>  	}
>>
>> -	graph_pad_horizontally(graph, sb, chars_written);
>> +	graph_pad_horizontally(graph, sb);
>>
>>  	/*
>>  	 * Update graph->state
>> @@ -984,12 +975,11 @@ static struct column *find_new_column_by_commit(struct git_graph *graph,
>>  static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
>>  {
>>  	int seen_this = 0;
>> -	int i, j, chars_written;
>> +	int i, j;
>>
>>  	/*
>>  	 * Output the post-merge row
>>  	 */
>> -	chars_written = 0;
>>  	for (i = 0; i <= graph->num_columns; i++) {
>>  		struct column *col = &graph->columns[i];
>>  		struct commit *col_commit;
>> @@ -1017,7 +1007,6 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
>>  			assert(par_column);
>>
>>  			strbuf_write_column(sb, par_column, '|');
>> -			chars_written++;
>>  			for (j = 0; j < graph->num_parents - 1; j++) {
>>  				parents = next_interesting_parent(graph, parents);
>>  				assert(parents);
>> @@ -1026,19 +1015,16 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
>>  				strbuf_write_column(sb, par_column, '\\');
>>  				strbuf_addch(sb, ' ');
>>  			}
>> -			chars_written += j * 2;
>>  		} else if (seen_this) {
>>  			strbuf_write_column(sb, col, '\\');
>>  			strbuf_addch(sb, ' ');
>> -			chars_written += 2;
>>  		} else {
>>  			strbuf_write_column(sb, col, '|');
>>  			strbuf_addch(sb, ' ');
>> -			chars_written += 2;
>>  		}
>>  	}
>>
>> -	graph_pad_horizontally(graph, sb, chars_written);
>> +	graph_pad_horizontally(graph, sb);
>>
>>  	/*
>>  	 * Update graph->state
>> @@ -1181,7 +1167,7 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
>>  		}
>>  	}
>>
>> -	graph_pad_horizontally(graph, sb, graph->mapping_size);
>> +	graph_pad_horizontally(graph, sb);
>>
>>  	/*
>>  	 * Swap mapping and new_mapping
>> @@ -1199,6 +1185,8 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
>>
>>  int graph_next_line(struct git_graph *graph, struct strbuf *sb)
>>  {
>> +	sb->width = 0;
>> +
>>  	switch (graph->state) {
>>  	case GRAPH_PADDING:
>>  		graph_output_padding_line(graph, sb);
>> @@ -1227,7 +1215,6 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb)
>>  static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
>>  {
>>  	int i;
>> -	int chars_written = 0;
>>
>>  	if (graph->state != GRAPH_COMMIT) {
>>  		graph_next_line(graph, sb);
>> @@ -1245,19 +1232,16 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
>>  		struct column *col = &graph->columns[i];
>>
>>  		strbuf_write_column(sb, col, '|');
>> -		chars_written++;
>>
>>  		if (col->commit == graph->commit && graph->num_parents > 2) {
>>  			int len = (graph->num_parents - 2) * 2;
>>  			strbuf_addchars(sb, ' ', len);
>> -			chars_written += len;
>>  		} else {
>>  			strbuf_addch(sb, ' ');
>> -			chars_written++;
>>  		}
>>  	}
>>
>> -	graph_pad_horizontally(graph, sb, chars_written);
>> +	graph_pad_horizontally(graph, sb);
>>
>>  	/*
>>  	 * Update graph->prev_state since we have output a padding line
>> diff --git a/strbuf.h b/strbuf.h
>> index f62278a0be..3a98147321 100644
>> --- a/strbuf.h
>> +++ b/strbuf.h
>> @@ -66,11 +66,12 @@ struct string_list;
>>  struct strbuf {
>>  	size_t alloc;
>>  	size_t len;
>> +	size_t width;
>>  	char *buf;
>>  };
>>
>>  extern char strbuf_slopbuf[];
>> -#define STRBUF_INIT  { .alloc = 0, .len = 0, .buf = strbuf_slopbuf }
>> +#define STRBUF_INIT  { .alloc = 0, .len = 0, .width = 0, .buf = strbuf_slopbuf }
>>
>>  /*
>>   * Predeclare this here, since cache.h includes this file before it defines the
>> @@ -161,6 +162,10 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len)
>>  {
>>  	if (len > (sb->alloc ? sb->alloc - 1 : 0))
>>  		die("BUG: strbuf_setlen() beyond buffer");
>> +	if (len > sb->len)
>> +		sb->width += len - sb->len;
>> +	else
>> +		sb->width = len;
>>  	sb->len = len;
>>  	if (sb->buf != strbuf_slopbuf)
>>  		sb->buf[len] = '\0';
>> @@ -231,6 +236,7 @@ static inline void strbuf_addch(struct strbuf *sb, int c)
>>  		strbuf_grow(sb, 1);
>>  	sb->buf[sb->len++] = c;
>>  	sb->buf[sb->len] = '\0';
>> +	sb->width++;
>>  }
>>
>>  /**
>> --
>> gitgitgadget
>>
>>

James Coglan Oct. 11, 2019, 5:20 p.m. UTC | #9

On 11/10/2019 17:02, Johannes Schindelin wrote:
> Hi,
> 
> On Thu, 10 Oct 2019, Denton Liu wrote:
> 
>> On Fri, Oct 11, 2019 at 10:42:20AM +0900, Junio C Hamano wrote:
>>> Denton Liu <[e-mail]> writes:
>>>
>>>> 	static int calculate_width(const struct strbuf *row)
>>>> 	{
>>>> 		int in_termcode = 0;
>>>> 		int width = 0;
>>>> 		int i;
>>>>
>>>> 		for (i = 0; i < row.len; i++) {
>>>> 			if (row.buf[i] == '\033')
>>>> 				in_termcode = 1;
>>>>
>>>> 			if (!in_termcode)
>>>> 				width++;
>>>> 			else if (row.buf[i] == 'm')
>>>> 				in_termcode = 0;
>>>> 		}
>>>> 	}
>>>
>>> Not every byte that is outside the escape sequence contributes to
>>> one display columns.  You would want to take a look at utf8_width()
>>> for inspiration.
>>>
>>
>> Heh, I guess you're right. Looking right below the definition of
>> utf8_width, I realised we have the utf8_strnwidth function. We should be
>> able to just call
>>
>> 	utf8_strnwidth(row.buf, row.len, 1);
> 
> Correct me if I'm wrong, but don't we want to keep track of the columns
> *only* in the part with the actual line graph, i.e. we're not at all
> interested in the onelines' widths?
> 
> If so, I could imagine that a good idea would be to introduce
> 
> 	struct graphbuf {
> 		struct strbuf buf;
> 		int width;
> 	};
> 
> and then introduce wrappers for `_addch()` and whatever else is used in
> `graph.c`, these wrappers will increment the width together with the
> `buf.len` field, and one additional helper that adds color sequences to
> that graphbuf that leaves `width` unchanged.

That's exactly what I've spent this afternoon doing, in response to the feedback here. I took into consideration that:

- We don't want a general solution to this problem for everything `strbuf` could be used for; it only needs to address the graph padding problem.

- We only want to count printing characters, not color formatting sequences.

- We only need to consider the width of a small set of characters: { | / \ _ - . * }. We don't need to worry about Unicode, and the simple character counting in graph.c was working fine.

- Attempting to count the characters in a `strbuf` after the fact is problematic, because sometimes the line prefix (`diff_options.line_prefix`) is included when `graph_pad_horizontally()` is called, and sometimes the prefix has already been sent to stdout and is not included in the `strbuf`. We need to know how many printing characters were added only during `graph_next_line()`.

To this end I've prepared a different implementation that introduces the indirection described above, and does not modify `strbuf`:

diff --git a/graph.c b/graph.c
index f53135485f..24bf1f4fe1 100644
--- a/graph.c
+++ b/graph.c
@@ -112,14 +112,38 @@ static const char *column_get_color_code(unsigned short color)
 	return column_colors[color];
 }
 
-static void strbuf_write_column(struct strbuf *sb, const struct column *c,
-				char col_char)
+struct graph_strbuf {
+	struct strbuf *buf;
+	size_t width;
+};
+
+static inline void graph_strbuf_addch(struct graph_strbuf *sb, int c)
+{
+	strbuf_addch(sb->buf, c);
+	sb->width++;
+}
+
+void graph_strbuf_addchars(struct graph_strbuf *sb, int c, size_t n)
+{
+	strbuf_addchars(sb->buf, c, n);
+	sb->width += n;
+}
+
+static inline void graph_strbuf_addstr(struct graph_strbuf *sb, const char *s)
+{
+	strbuf_addstr(sb->buf, s);
+	sb->width += strlen(s);
+}
+
+static void graph_strbuf_write_column(struct graph_strbuf *sb, const struct column *c,
+				      char col_char)
 {
 	if (c->color < column_colors_max)
-		strbuf_addstr(sb, column_get_color_code(c->color));
-	strbuf_addch(sb, col_char);
+		strbuf_addstr(sb->buf, column_get_color_code(c->color));
+	strbuf_addch(sb->buf, col_char);
+	sb->width++;
 	if (c->color < column_colors_max)
-		strbuf_addstr(sb, column_get_color_code(column_colors_max));
+		strbuf_addstr(sb->buf, column_get_color_code(column_colors_max));
 }
 
 struct git_graph {
@@ -686,8 +710,7 @@ static int graph_is_mapping_correct(struct git_graph *graph)
 	return 1;
 }
 
-static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
-				   int chars_written)
+static void graph_pad_horizontally(struct git_graph *graph, struct graph_strbuf *sb)
 {
 	/*
 	 * Add additional spaces to the end of the strbuf, so that all
@@ -696,12 +719,12 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
 	 * This way, fields printed to the right of the graph will remain
 	 * aligned for the entire commit.
 	 */
-	if (chars_written < graph->width)
-		strbuf_addchars(sb, ' ', graph->width - chars_written);
+	if (sb->width < graph->width)
+		strbuf_addchars(sb->buf, ' ', graph->width - sb->width);
 }
 
 static void graph_output_padding_line(struct git_graph *graph,
-				      struct strbuf *sb)
+				      struct graph_strbuf *sb)
 {
 	int i;
 
@@ -719,11 +742,11 @@ static void graph_output_padding_line(struct git_graph *graph,
 	 * Output a padding row, that leaves all branch lines unchanged
 	 */
 	for (i = 0; i < graph->num_new_columns; i++) {
-		strbuf_write_column(sb, &graph->new_columns[i], '|');
-		strbuf_addch(sb, ' ');
+		graph_strbuf_write_column(sb, &graph->new_columns[i], '|');
+		graph_strbuf_addch(sb, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
+	graph_pad_horizontally(graph, sb);
 }
 
 
@@ -733,14 +756,14 @@ int graph_width(struct git_graph *graph)
 }
 
 
-static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_skip_line(struct git_graph *graph, struct graph_strbuf *sb)
 {
 	/*
 	 * Output an ellipsis to indicate that a portion
 	 * of the graph is missing.
 	 */
-	strbuf_addstr(sb, "...");
-	graph_pad_horizontally(graph, sb, 3);
+	graph_strbuf_addstr(sb, "...");
+	graph_pad_horizontally(graph, sb);
 
 	if (graph->num_parents >= 3 &&
 	    graph->commit_index < (graph->num_columns - 1))
@@ -750,11 +773,10 @@ static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
 }
 
 static void graph_output_pre_commit_line(struct git_graph *graph,
-					 struct strbuf *sb)
+					 struct graph_strbuf *sb)
 {
 	int num_expansion_rows;
 	int i, seen_this;
-	int chars_written;
 
 	/*
 	 * This function formats a row that increases the space around a commit
@@ -777,14 +799,12 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 	 * Output the row
 	 */
 	seen_this = 0;
-	chars_written = 0;
 	for (i = 0; i < graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		if (col->commit == graph->commit) {
 			seen_this = 1;
-			strbuf_write_column(sb, col, '|');
-			strbuf_addchars(sb, ' ', graph->expansion_row);
-			chars_written += 1 + graph->expansion_row;
+			graph_strbuf_write_column(sb, col, '|');
+			graph_strbuf_addchars(sb, ' ', graph->expansion_row);
 		} else if (seen_this && (graph->expansion_row == 0)) {
 			/*
 			 * This is the first line of the pre-commit output.
@@ -797,22 +817,18 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				strbuf_write_column(sb, col, '\\');
+				graph_strbuf_write_column(sb, col, '\\');
 			else
-				strbuf_write_column(sb, col, '|');
-			chars_written++;
+				graph_strbuf_write_column(sb, col, '|');
 		} else if (seen_this && (graph->expansion_row > 0)) {
-			strbuf_write_column(sb, col, '\\');
-			chars_written++;
+			graph_strbuf_write_column(sb, col, '\\');
 		} else {
-			strbuf_write_column(sb, col, '|');
-			chars_written++;
+			graph_strbuf_write_column(sb, col, '|');
 		}
-		strbuf_addch(sb, ' ');
-		chars_written++;
+		graph_strbuf_addch(sb, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, sb);
 
 	/*
 	 * Increment graph->expansion_row,
@@ -823,7 +839,7 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		graph_update_state(graph, GRAPH_COMMIT);
 }
 
-static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_commit_char(struct git_graph *graph, struct graph_strbuf *sb)
 {
 	/*
 	 * For boundary commits, print 'o'
@@ -831,22 +847,20 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 	 */
 	if (graph->commit->object.flags & BOUNDARY) {
 		assert(graph->revs->boundary);
-		strbuf_addch(sb, 'o');
+		graph_strbuf_addch(sb, 'o');
 		return;
 	}
 
 	/*
 	 * get_revision_mark() handles all other cases without assert()
 	 */
-	strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
+	graph_strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
 }
 
 /*
- * Draw the horizontal dashes of an octopus merge and return the number of
- * characters written.
+ * Draw the horizontal dashes of an octopus merge.
  */
-static int graph_draw_octopus_merge(struct git_graph *graph,
-				    struct strbuf *sb)
+static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_strbuf *sb)
 {
 	/*
 	 * Here dashless_parents represents the number of parents which don't
@@ -886,17 +900,16 @@ static int graph_draw_octopus_merge(struct git_graph *graph,
 
 	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 ? '.' : '-');
+		graph_strbuf_write_column(sb, &graph->new_columns[i+first_col], '-');
+		graph_strbuf_write_column(sb, &graph->new_columns[i+first_col],
+					  i == dashful_parents-1 ? '.' : '-');
 	}
-	return 2 * dashful_parents;
 }
 
-static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_commit_line(struct git_graph *graph, struct graph_strbuf *sb)
 {
 	int seen_this = 0;
-	int i, chars_written;
+	int i;
 
 	/*
 	 * Output the row containing this commit
@@ -906,7 +919,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 	 * children that we have already processed.)
 	 */
 	seen_this = 0;
-	chars_written = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
@@ -921,14 +933,11 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 		if (col_commit == graph->commit) {
 			seen_this = 1;
 			graph_output_commit_char(graph, sb);
-			chars_written++;
 
 			if (graph->num_parents > 2)
-				chars_written += graph_draw_octopus_merge(graph,
-									  sb);
+				graph_draw_octopus_merge(graph, sb);
 		} else if (seen_this && (graph->num_parents > 2)) {
-			strbuf_write_column(sb, col, '\\');
-			chars_written++;
+			graph_strbuf_write_column(sb, col, '\\');
 		} else if (seen_this && (graph->num_parents == 2)) {
 			/*
 			 * This is a 2-way merge commit.
@@ -945,19 +954,16 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				strbuf_write_column(sb, col, '\\');
+				graph_strbuf_write_column(sb, col, '\\');
 			else
-				strbuf_write_column(sb, col, '|');
-			chars_written++;
+				graph_strbuf_write_column(sb, col, '|');
 		} else {
-			strbuf_write_column(sb, col, '|');
-			chars_written++;
+			graph_strbuf_write_column(sb, col, '|');
 		}
-		strbuf_addch(sb, ' ');
-		chars_written++;
+		graph_strbuf_addch(sb, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, sb);
 
 	/*
 	 * Update graph->state
@@ -981,15 +987,14 @@ static struct column *find_new_column_by_commit(struct git_graph *graph,
 	return NULL;
 }
 
-static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_post_merge_line(struct git_graph *graph, struct graph_strbuf *sb)
 {
 	int seen_this = 0;
-	int i, j, chars_written;
+	int i, j;
 
 	/*
 	 * Output the post-merge row
 	 */
-	chars_written = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
@@ -1016,29 +1021,25 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 			par_column = find_new_column_by_commit(graph, parents->item);
 			assert(par_column);
 
-			strbuf_write_column(sb, par_column, '|');
-			chars_written++;
+			graph_strbuf_write_column(sb, par_column, '|');
 			for (j = 0; j < graph->num_parents - 1; j++) {
 				parents = next_interesting_parent(graph, parents);
 				assert(parents);
 				par_column = find_new_column_by_commit(graph, parents->item);
 				assert(par_column);
-				strbuf_write_column(sb, par_column, '\\');
-				strbuf_addch(sb, ' ');
+				graph_strbuf_write_column(sb, par_column, '\\');
+				graph_strbuf_addch(sb, ' ');
 			}
-			chars_written += j * 2;
 		} else if (seen_this) {
-			strbuf_write_column(sb, col, '\\');
-			strbuf_addch(sb, ' ');
-			chars_written += 2;
+			graph_strbuf_write_column(sb, col, '\\');
+			graph_strbuf_addch(sb, ' ');
 		} else {
-			strbuf_write_column(sb, col, '|');
-			strbuf_addch(sb, ' ');
-			chars_written += 2;
+			graph_strbuf_write_column(sb, col, '|');
+			graph_strbuf_addch(sb, ' ');
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, sb);
 
 	/*
 	 * Update graph->state
@@ -1049,7 +1050,7 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
-static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_collapsing_line(struct git_graph *graph, struct graph_strbuf *sb)
 {
 	int i;
 	short used_horizontal = 0;
@@ -1159,9 +1160,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 	for (i = 0; i < graph->mapping_size; i++) {
 		int target = graph->new_mapping[i];
 		if (target < 0)
-			strbuf_addch(sb, ' ');
+			graph_strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
-			strbuf_write_column(sb, &graph->new_columns[target], '|');
+			graph_strbuf_write_column(sb, &graph->new_columns[target], '|');
 		else if (target == horizontal_edge_target &&
 			 i != horizontal_edge - 1) {
 				/*
@@ -1172,16 +1173,16 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 				if (i != (target * 2)+3)
 					graph->new_mapping[i] = -1;
 				used_horizontal = 1;
-			strbuf_write_column(sb, &graph->new_columns[target], '_');
+			graph_strbuf_write_column(sb, &graph->new_columns[target], '_');
 		} else {
 			if (used_horizontal && i < horizontal_edge)
 				graph->new_mapping[i] = -1;
-			strbuf_write_column(sb, &graph->new_columns[target], '/');
+			graph_strbuf_write_column(sb, &graph->new_columns[target], '/');
 
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, graph->mapping_size);
+	graph_pad_horizontally(graph, sb);
 
 	/*
 	 * Swap mapping and new_mapping
@@ -1199,24 +1200,26 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 
 int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 {
+	struct graph_strbuf gsb = { .buf = sb, .width = 0 };
+
 	switch (graph->state) {
 	case GRAPH_PADDING:
-		graph_output_padding_line(graph, sb);
+		graph_output_padding_line(graph, &gsb);
 		return 0;
 	case GRAPH_SKIP:
-		graph_output_skip_line(graph, sb);
+		graph_output_skip_line(graph, &gsb);
 		return 0;
 	case GRAPH_PRE_COMMIT:
-		graph_output_pre_commit_line(graph, sb);
+		graph_output_pre_commit_line(graph, &gsb);
 		return 0;
 	case GRAPH_COMMIT:
-		graph_output_commit_line(graph, sb);
+		graph_output_commit_line(graph, &gsb);
 		return 1;
 	case GRAPH_POST_MERGE:
-		graph_output_post_merge_line(graph, sb);
+		graph_output_post_merge_line(graph, &gsb);
 		return 0;
 	case GRAPH_COLLAPSING:
-		graph_output_collapsing_line(graph, sb);
+		graph_output_collapsing_line(graph, &gsb);
 		return 0;
 	}
 
@@ -1227,7 +1230,7 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int i;
-	int chars_written = 0;
+	struct graph_strbuf gsb = { .buf = sb, .width = 0 };
 
 	if (graph->state != GRAPH_COMMIT) {
 		graph_next_line(graph, sb);
@@ -1244,20 +1247,17 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 	for (i = 0; i < graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 
-		strbuf_write_column(sb, col, '|');
-		chars_written++;
+		graph_strbuf_write_column(&gsb, col, '|');
 
 		if (col->commit == graph->commit && graph->num_parents > 2) {
 			int len = (graph->num_parents - 2) * 2;
-			strbuf_addchars(sb, ' ', len);
-			chars_written += len;
+			graph_strbuf_addchars(&gsb, ' ', len);
 		} else {
-			strbuf_addch(sb, ' ');
-			chars_written++;
+			graph_strbuf_addch(&gsb, ' ');
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, &gsb);
 
 	/*
 	 * Update graph->prev_state since we have output a padding line

Junio C Hamano Oct. 12, 2019, 12:27 a.m. UTC | #10

James Coglan <[e-mail]> writes:

> - We don't want a general solution to this problem for everything
> `strbuf` could be used for; it only needs to address the graph
> padding problem.

Of course.  Somebody may use strbuf to hold rows of a table and you
do not want to contaminate strbuf with fields like width of each
column etc, that are very specific to the application.  IOW, strbuf
is merely _one_ component of a larger solution to each specific
problem, and the latter may be things like "struct graphbuf" like
Dscho suggested, which might use strbuf as an underlying
<byte-string, length> tuple mechanism, but that is an implementation
detail that should not be exposed to the users of the struct (and
that is why he did not call, and you should not call, the data
structure "graph-strbuf" or anything with "strbuf").

> - We only want to count printing characters, not color formatting sequences.

OK.  But I'd phrase "count printing characters" as "measure display
width" for at least two reasons.  Whitespaces are typically counted
as non-printing, but you do want to take them into account for this
application.  Also the graph may not be limited to ASCII graphics
forever, and byte- or character-count may not match display width on
a fixed-width display.

> - We only need to consider the width of a small set of characters:
> { | / \ _ - . * }. We don't need to worry about Unicode, and the
> simple character counting in graph.c was working fine.

I have to warn you that we saw attempts to step outside these ASCII
graphics and use Unicode characters for prettier output in the past.
If you can do so without too much complexity, I'd suggest you try
not to close the door to those people who follow your footsteps to
further improve the system by pursuing the avenue further.

> To this end I've prepared a different implementation that
> introduces the indirection described above, and does not modify
> `strbuf`:
>
> +struct graph_strbuf {
> +	struct strbuf *buf;
> +	size_t width;
> +};

Is there a reason why you need a pointer to a strbuf that is
allocated separately?  E.g. would it make it harder to manage
if the above were

	struct graphbuf {
		struct strbuf buf;
		int width; /* display width in columns */
	};

which is essentially what Dscho suggested?

> +static inline void graph_strbuf_addch(struct graph_strbuf *sb, int c)
> +{
> +	strbuf_addch(sb->buf, c);
> +	sb->width++;
> +}
> +
> +void graph_strbuf_addchars(struct graph_strbuf *sb, int c, size_t n)
> +{
> +	strbuf_addchars(sb->buf, c, n);
> +	sb->width += n;
> +}
> +
> +static inline void graph_strbuf_addstr(struct graph_strbuf *sb, const char *s)
> +{
> +	strbuf_addstr(sb->buf, s);
> +	sb->width += strlen(s);
> +}

I'd probably introduce another helper that takes color code and
graphbuf (also notice how I name the variables and types; calling
something sb that is not a strbuf is misleading and inviting
unnecessary bugs):

    static inline void graphbuf_addcolor(struct graphbuf *gb, unsigned short color)
    {
            strbuf_addstr(gb->buf, column_get_color_code(color));
    }

if I were writing this code.  The goal is to make any strbuf_add*()
that is done directly on gb->buf outside these helpers a bug--that
way, grepping for strbuf_add* in this file would become a very easy
way to catch such a bug that bypasses the graphbuf_add*() layer and
potentially screw up the column counting.

Other than these three points (i.e. naming without "strbuf" that is
an implementation detail, embedded vs pointer of strbuf in the
graphbuf, and making sure everything can be done via graphbuf_add*()
wrappers to make it easier to spot bugs), it seems you are going in
the right direction.  Thanks for working on this.

Johannes Schindelin Oct. 12, 2019, 4:22 p.m. UTC | #11

Hi,

I just realized that I completely failed to offer my enthusiasm not only
for the idea of this patch series and the resulting graphs, but also at
the really high quality of the contribution. Thanks, James, for working
on this!

And now just quickly...

On Sat, 12 Oct 2019, Junio C Hamano wrote:

> James Coglan <[e-mail]> writes:
>
> > - We only need to consider the width of a small set of characters:
> > { | / \ _ - . * }. We don't need to worry about Unicode, and the
> > simple character counting in graph.c was working fine.
>
> I have to warn you that we saw attempts to step outside these ASCII
> graphics and use Unicode characters for prettier output in the past.
> If you can do so without too much complexity, I'd suggest you try
> not to close the door to those people who follow your footsteps to
> further improve the system by pursuing the avenue further.

That is a very valid point, I think. There are really pretty Unicode
characters out there that I could totally see in a nice commit graph.

At that stage, we would have to use `int utf8_strnwidth(const char
*string, int len, int skip_ansi)` anyway (because of the `skip_ansi`
that saves us _a lot_ of work). In this case, I doubt that it makes
sense to keep a running tally of the width. It would be faster, or at
least similarly fast, to just run `utf8_strnwidth()` on the final string
that we want to measure.

Ciao,
Dscho

James Coglan Oct. 14, 2019, 12:55 p.m. UTC | #12

On 12/10/2019 01:27, Junio C Hamano wrote:
> James Coglan <[e-mail]> writes:
> 
>> - We don't want a general solution to this problem for everything
>> `strbuf` could be used for; it only needs to address the graph
>> padding problem.
> 
> Of course.  Somebody may use strbuf to hold rows of a table and you
> do not want to contaminate strbuf with fields like width of each
> column etc, that are very specific to the application.  IOW, strbuf
> is merely _one_ component of a larger solution to each specific
> problem, and the latter may be things like "struct graphbuf" like
> Dscho suggested, which might use strbuf as an underlying
> <byte-string, length> tuple mechanism, but that is an implementation
> detail that should not be exposed to the users of the struct (and
> that is why he did not call, and you should not call, the data
> structure "graph-strbuf" or anything with "strbuf").

Thank you for the clarification. I've now modified my patch to call the wrapper struct `graph_line` to better reflect its use. This was informed by uncertainty on this thread about whether the width calculation needs to take line breaks into account, so I wanted to name it to indicate it contains a single display line.

>> - We only want to count printing characters, not color formatting sequences.
> 
> OK.  But I'd phrase "count printing characters" as "measure display
> width" for at least two reasons.  Whitespaces are typically counted
> as non-printing, but you do want to take them into account for this
> application.  Also the graph may not be limited to ASCII graphics
> forever, and byte- or character-count may not match display width on
> a fixed-width display.
> 
>> - We only need to consider the width of a small set of characters:
>> { | / \ _ - . * }. We don't need to worry about Unicode, and the
>> simple character counting in graph.c was working fine.
> 
> I have to warn you that we saw attempts to step outside these ASCII
> graphics and use Unicode characters for prettier output in the past.
> If you can do so without too much complexity, I'd suggest you try
> not to close the door to those people who follow your footsteps to
> further improve the system by pursuing the avenue further.

That makes sense. All I've done for now is to put the calculations that were already being done behind an interface, consisting of just the operations graph.c actually uses, namely:

void graph_line_addch(struct graph_line *line, int c);

void graph_line_addchars(struct graph_line *line, int c, size_t n);

void graph_line_addstr(struct graph_line *line, const char *s);

void graph_line_write_column(struct graph_line *line, const struct column *c, char col_char);

Having this interface in place should not preclude extending this functionality to Unicode later, and may make it simpler as it puts all the disply width calculations in one place, rather than its current state where it's distributed across all the output functions and makes the assumption that all chars contribute one display column. It especially removes the need for statements like this that encode an assumption about what was printed:

    graph_pad_horizontally(graph, sb, graph->num_columns * 2);

>> To this end I've prepared a different implementation that
>> introduces the indirection described above, and does not modify
>> `strbuf`:
>>
>> +struct graph_strbuf {
>> +	struct strbuf *buf;
>> +	size_t width;
>> +};
> 
> Is there a reason why you need a pointer to a strbuf that is
> allocated separately?  E.g. would it make it harder to manage
> if the above were
> 
> 	struct graphbuf {
> 		struct strbuf buf;
> 		int width; /* display width in columns */
> 	};
> 
> which is essentially what Dscho suggested?

I used a pointer here because I create the wrapper struct in `graph_next_line()`, which is an external interface that takes a `struct strbuf *`:

int graph_next_line(struct git_graph *graph, struct strbuf *sb)
{
	struct graph_line line = { .buf = sb, .width = 0 };
	// ...
}

So I'm not allocating the strbuf here, just wrapping a pointer to it. I would prefer to define `graph_line` as having a `strbuf` inline but I've not found a way to do that without breaking the other functions that call `graph_next_line()`. Although, as far as I know both this wrapper struct and every `strbuf` it points to are stack-allocated so I'm more concerned about the extra dereference rather than allocation cost.

If there's a way to do this I'm open to suggestions.

>> +static inline void graph_strbuf_addch(struct graph_strbuf *sb, int c)
>> +{
>> +	strbuf_addch(sb->buf, c);
>> +	sb->width++;
>> +}
>> +
>> +void graph_strbuf_addchars(struct graph_strbuf *sb, int c, size_t n)
>> +{
>> +	strbuf_addchars(sb->buf, c, n);
>> +	sb->width += n;
>> +}
>> +
>> +static inline void graph_strbuf_addstr(struct graph_strbuf *sb, const char *s)
>> +{
>> +	strbuf_addstr(sb->buf, s);
>> +	sb->width += strlen(s);
>> +}
> 
> I'd probably introduce another helper that takes color code and
> graphbuf (also notice how I name the variables and types; calling
> something sb that is not a strbuf is misleading and inviting
> unnecessary bugs):
> 
>     static inline void graphbuf_addcolor(struct graphbuf *gb, unsigned short color)
>     {
>             strbuf_addstr(gb->buf, column_get_color_code(color));
>     }
> 
> if I were writing this code.  The goal is to make any strbuf_add*()
> that is done directly on gb->buf outside these helpers a bug--that
> way, grepping for strbuf_add* in this file would become a very easy
> way to catch such a bug that bypasses the graphbuf_add*() layer and
> potentially screw up the column counting.

That would be great, I'm just not sure how to fully decouple graph.c from `strbuf` so that I can properly block it from using the `strbuf` interface. What I have done is got a better separation between uses of `strbuf` and `graph_line`, so that the only functions that still use the `strbuf` interface are the `graph_line` interface, and functions that create a `strbuf` themselves (e.g. `graph_show_commit()`). Hopefully that separation makes the intent clearer and is a stepping stone to fully decoupling these interfaces.

> Other than these three points (i.e. naming without "strbuf" that is
> an implementation detail, embedded vs pointer of strbuf in the
> graphbuf, and making sure everything can be done via graphbuf_add*()
> wrappers to make it easier to spot bugs), it seems you are going in
> the right direction.  Thanks for working on this.

Thanks! For completeness, here is the current state of this patch after I've been through the feedback up to this point:

From 241180570fbaae04a2263c5ff1ab3b92f54f8004 Mon Sep 17 00:00:00 2001
From: James Coglan <[e-mail]>
Date: Thu, 22 Aug 2019 09:30:08 +0100
Subject: [PATCH] graph: automatically track display width of graph lines

All the output functions called by `graph_next_line()` currently keep
track of how many printable chars they've written to the buffer, before
calling `graph_pad_horizontally()` to pad the line with spaces. Some
functions do this by incrementing a counter whenever they write to the
buffer, and others do it by encoding an assumption about how many chars
are written, as in:

    graph_pad_horizontally(graph, sb, graph->num_columns * 2);

This adds a fair amount of noise to the functions' logic and is easily
broken if one forgets to increment the right counter or update the
calculations used for padding.

To make this easier to use, I'm introducing a new struct called
`graph_line` that wraps a `strbuf` and keeps count of its display width
implicitly. `graph_next_line()` wraps this around the `struct strbuf *`
it's given and passes a `struct graph_line *` to the output functions,
which use its interface.

The `graph_line` interface wraps the `strbuf_addch()`,
`strbuf_addchars()` and `strbuf_addstr()` functions, and adds the
`graph_line_write_column()` function for adding a single character with
color formatting. The `graph_pad_horizontally()` function can then use
the `width` field from the struct rather than taking a character count
as a parameter.

Signed-off-by: James Coglan <[e-mail]>
---
 graph.c | 194 +++++++++++++++++++++++++++++---------------------------
 1 file changed, 99 insertions(+), 95 deletions(-)

diff --git a/graph.c b/graph.c
index f53135485f..2f81a5d23d 100644
--- a/graph.c
+++ b/graph.c
@@ -112,14 +112,42 @@ static const char *column_get_color_code(unsigned short color)
 	return column_colors[color];
 }
 
-static void strbuf_write_column(struct strbuf *sb, const struct column *c,
-				char col_char)
+struct graph_line {
+	struct strbuf *buf;
+	size_t width;
+};
+
+static inline void graph_line_addch(struct graph_line *line, int c)
+{
+	strbuf_addch(line->buf, c);
+	line->width++;
+}
+
+static inline void graph_line_addchars(struct graph_line *line, int c, size_t n)
+{
+	strbuf_addchars(line->buf, c, n);
+	line->width += n;
+}
+
+static inline void graph_line_addstr(struct graph_line *line, const char *s)
+{
+	strbuf_addstr(line->buf, s);
+	line->width += strlen(s);
+}
+
+static inline void graph_line_addcolor(struct graph_line *line, unsigned short color)
+{
+	strbuf_addstr(line->buf, column_get_color_code(color));
+}
+
+static void graph_line_write_column(struct graph_line *line, const struct column *c,
+				    char col_char)
 {
 	if (c->color < column_colors_max)
-		strbuf_addstr(sb, column_get_color_code(c->color));
-	strbuf_addch(sb, col_char);
+		graph_line_addcolor(line, c->color);
+	graph_line_addch(line, col_char);
 	if (c->color < column_colors_max)
-		strbuf_addstr(sb, column_get_color_code(column_colors_max));
+		graph_line_addcolor(line, column_colors_max);
 }
 
 struct git_graph {
@@ -686,8 +714,7 @@ static int graph_is_mapping_correct(struct git_graph *graph)
 	return 1;
 }
 
-static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
-				   int chars_written)
+static void graph_pad_horizontally(struct git_graph *graph, struct graph_line *line)
 {
 	/*
 	 * Add additional spaces to the end of the strbuf, so that all
@@ -696,12 +723,12 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
 	 * This way, fields printed to the right of the graph will remain
 	 * aligned for the entire commit.
 	 */
-	if (chars_written < graph->width)
-		strbuf_addchars(sb, ' ', graph->width - chars_written);
+	if (line->width < graph->width)
+		graph_line_addchars(line, ' ', graph->width - line->width);
 }
 
 static void graph_output_padding_line(struct git_graph *graph,
-				      struct strbuf *sb)
+				      struct graph_line *line)
 {
 	int i;
 
@@ -719,11 +746,11 @@ static void graph_output_padding_line(struct git_graph *graph,
 	 * Output a padding row, that leaves all branch lines unchanged
 	 */
 	for (i = 0; i < graph->num_new_columns; i++) {
-		strbuf_write_column(sb, &graph->new_columns[i], '|');
-		strbuf_addch(sb, ' ');
+		graph_line_write_column(line, &graph->new_columns[i], '|');
+		graph_line_addch(line, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
+	graph_pad_horizontally(graph, line);
 }
 
 
@@ -733,14 +760,14 @@ int graph_width(struct git_graph *graph)
 }
 
 
-static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_skip_line(struct git_graph *graph, struct graph_line *line)
 {
 	/*
 	 * Output an ellipsis to indicate that a portion
 	 * of the graph is missing.
 	 */
-	strbuf_addstr(sb, "...");
-	graph_pad_horizontally(graph, sb, 3);
+	graph_line_addstr(line, "...");
+	graph_pad_horizontally(graph, line);
 
 	if (graph->num_parents >= 3 &&
 	    graph->commit_index < (graph->num_columns - 1))
@@ -750,11 +777,10 @@ static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
 }
 
 static void graph_output_pre_commit_line(struct git_graph *graph,
-					 struct strbuf *sb)
+					 struct graph_line *line)
 {
 	int num_expansion_rows;
 	int i, seen_this;
-	int chars_written;
 
 	/*
 	 * This function formats a row that increases the space around a commit
@@ -777,14 +803,12 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 	 * Output the row
 	 */
 	seen_this = 0;
-	chars_written = 0;
 	for (i = 0; i < graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		if (col->commit == graph->commit) {
 			seen_this = 1;
-			strbuf_write_column(sb, col, '|');
-			strbuf_addchars(sb, ' ', graph->expansion_row);
-			chars_written += 1 + graph->expansion_row;
+			graph_line_write_column(line, col, '|');
+			graph_line_addchars(line, ' ', graph->expansion_row);
 		} else if (seen_this && (graph->expansion_row == 0)) {
 			/*
 			 * This is the first line of the pre-commit output.
@@ -797,22 +821,18 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				strbuf_write_column(sb, col, '\\');
+				graph_line_write_column(line, col, '\\');
 			else
-				strbuf_write_column(sb, col, '|');
-			chars_written++;
+				graph_line_write_column(line, col, '|');
 		} else if (seen_this && (graph->expansion_row > 0)) {
-			strbuf_write_column(sb, col, '\\');
-			chars_written++;
+			graph_line_write_column(line, col, '\\');
 		} else {
-			strbuf_write_column(sb, col, '|');
-			chars_written++;
+			graph_line_write_column(line, col, '|');
 		}
-		strbuf_addch(sb, ' ');
-		chars_written++;
+		graph_line_addch(line, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, line);
 
 	/*
 	 * Increment graph->expansion_row,
@@ -823,7 +843,7 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		graph_update_state(graph, GRAPH_COMMIT);
 }
 
-static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_commit_char(struct git_graph *graph, struct graph_line *line)
 {
 	/*
 	 * For boundary commits, print 'o'
@@ -831,22 +851,20 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 	 */
 	if (graph->commit->object.flags & BOUNDARY) {
 		assert(graph->revs->boundary);
-		strbuf_addch(sb, 'o');
+		graph_line_addch(line, 'o');
 		return;
 	}
 
 	/*
 	 * get_revision_mark() handles all other cases without assert()
 	 */
-	strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
+	graph_line_addstr(line, get_revision_mark(graph->revs, graph->commit));
 }
 
 /*
- * Draw the horizontal dashes of an octopus merge and return the number of
- * characters written.
+ * Draw the horizontal dashes of an octopus merge.
  */
-static int graph_draw_octopus_merge(struct git_graph *graph,
-				    struct strbuf *sb)
+static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line *line)
 {
 	/*
 	 * Here dashless_parents represents the number of parents which don't
@@ -886,17 +904,16 @@ static int graph_draw_octopus_merge(struct git_graph *graph,
 
 	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 ? '.' : '-');
+		graph_line_write_column(line, &graph->new_columns[i+first_col], '-');
+		graph_line_write_column(line, &graph->new_columns[i+first_col],
+					  i == dashful_parents-1 ? '.' : '-');
 	}
-	return 2 * dashful_parents;
 }
 
-static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_commit_line(struct git_graph *graph, struct graph_line *line)
 {
 	int seen_this = 0;
-	int i, chars_written;
+	int i;
 
 	/*
 	 * Output the row containing this commit
@@ -906,7 +923,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 	 * children that we have already processed.)
 	 */
 	seen_this = 0;
-	chars_written = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
@@ -920,15 +936,12 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 
 		if (col_commit == graph->commit) {
 			seen_this = 1;
-			graph_output_commit_char(graph, sb);
-			chars_written++;
+			graph_output_commit_char(graph, line);
 
 			if (graph->num_parents > 2)
-				chars_written += graph_draw_octopus_merge(graph,
-									  sb);
+				graph_draw_octopus_merge(graph, line);
 		} else if (seen_this && (graph->num_parents > 2)) {
-			strbuf_write_column(sb, col, '\\');
-			chars_written++;
+			graph_line_write_column(line, col, '\\');
 		} else if (seen_this && (graph->num_parents == 2)) {
 			/*
 			 * This is a 2-way merge commit.
@@ -945,19 +958,16 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				strbuf_write_column(sb, col, '\\');
+				graph_line_write_column(line, col, '\\');
 			else
-				strbuf_write_column(sb, col, '|');
-			chars_written++;
+				graph_line_write_column(line, col, '|');
 		} else {
-			strbuf_write_column(sb, col, '|');
-			chars_written++;
+			graph_line_write_column(line, col, '|');
 		}
-		strbuf_addch(sb, ' ');
-		chars_written++;
+		graph_line_addch(line, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, line);
 
 	/*
 	 * Update graph->state
@@ -981,15 +991,14 @@ static struct column *find_new_column_by_commit(struct git_graph *graph,
 	return NULL;
 }
 
-static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_post_merge_line(struct git_graph *graph, struct graph_line *line)
 {
 	int seen_this = 0;
-	int i, j, chars_written;
+	int i, j;
 
 	/*
 	 * Output the post-merge row
 	 */
-	chars_written = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
@@ -1016,29 +1025,25 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 			par_column = find_new_column_by_commit(graph, parents->item);
 			assert(par_column);
 
-			strbuf_write_column(sb, par_column, '|');
-			chars_written++;
+			graph_line_write_column(line, par_column, '|');
 			for (j = 0; j < graph->num_parents - 1; j++) {
 				parents = next_interesting_parent(graph, parents);
 				assert(parents);
 				par_column = find_new_column_by_commit(graph, parents->item);
 				assert(par_column);
-				strbuf_write_column(sb, par_column, '\\');
-				strbuf_addch(sb, ' ');
+				graph_line_write_column(line, par_column, '\\');
+				graph_line_addch(line, ' ');
 			}
-			chars_written += j * 2;
 		} else if (seen_this) {
-			strbuf_write_column(sb, col, '\\');
-			strbuf_addch(sb, ' ');
-			chars_written += 2;
+			graph_line_write_column(line, col, '\\');
+			graph_line_addch(line, ' ');
 		} else {
-			strbuf_write_column(sb, col, '|');
-			strbuf_addch(sb, ' ');
-			chars_written += 2;
+			graph_line_write_column(line, col, '|');
+			graph_line_addch(line, ' ');
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, line);
 
 	/*
 	 * Update graph->state
@@ -1049,7 +1054,7 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
-static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
+static void graph_output_collapsing_line(struct git_graph *graph, struct graph_line *line)
 {
 	int i;
 	short used_horizontal = 0;
@@ -1159,9 +1164,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 	for (i = 0; i < graph->mapping_size; i++) {
 		int target = graph->new_mapping[i];
 		if (target < 0)
-			strbuf_addch(sb, ' ');
+			graph_line_addch(line, ' ');
 		else if (target * 2 == i)
-			strbuf_write_column(sb, &graph->new_columns[target], '|');
+			graph_line_write_column(line, &graph->new_columns[target], '|');
 		else if (target == horizontal_edge_target &&
 			 i != horizontal_edge - 1) {
 				/*
@@ -1172,16 +1177,16 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 				if (i != (target * 2)+3)
 					graph->new_mapping[i] = -1;
 				used_horizontal = 1;
-			strbuf_write_column(sb, &graph->new_columns[target], '_');
+			graph_line_write_column(line, &graph->new_columns[target], '_');
 		} else {
 			if (used_horizontal && i < horizontal_edge)
 				graph->new_mapping[i] = -1;
-			strbuf_write_column(sb, &graph->new_columns[target], '/');
+			graph_line_write_column(line, &graph->new_columns[target], '/');
 
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, graph->mapping_size);
+	graph_pad_horizontally(graph, line);
 
 	/*
 	 * Swap mapping and new_mapping
@@ -1199,24 +1204,26 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 
 int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 {
+	struct graph_line line = { .buf = sb, .width = 0 };
+
 	switch (graph->state) {
 	case GRAPH_PADDING:
-		graph_output_padding_line(graph, sb);
+		graph_output_padding_line(graph, &line);
 		return 0;
 	case GRAPH_SKIP:
-		graph_output_skip_line(graph, sb);
+		graph_output_skip_line(graph, &line);
 		return 0;
 	case GRAPH_PRE_COMMIT:
-		graph_output_pre_commit_line(graph, sb);
+		graph_output_pre_commit_line(graph, &line);
 		return 0;
 	case GRAPH_COMMIT:
-		graph_output_commit_line(graph, sb);
+		graph_output_commit_line(graph, &line);
 		return 1;
 	case GRAPH_POST_MERGE:
-		graph_output_post_merge_line(graph, sb);
+		graph_output_post_merge_line(graph, &line);
 		return 0;
 	case GRAPH_COLLAPSING:
-		graph_output_collapsing_line(graph, sb);
+		graph_output_collapsing_line(graph, &line);
 		return 0;
 	}
 
@@ -1227,7 +1234,7 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int i;
-	int chars_written = 0;
+	struct graph_line line = { .buf = sb, .width = 0 };
 
 	if (graph->state != GRAPH_COMMIT) {
 		graph_next_line(graph, sb);
@@ -1244,20 +1251,17 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 	for (i = 0; i < graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 
-		strbuf_write_column(sb, col, '|');
-		chars_written++;
+		graph_line_write_column(&line, col, '|');
 
 		if (col->commit == graph->commit && graph->num_parents > 2) {
 			int len = (graph->num_parents - 2) * 2;
-			strbuf_addchars(sb, ' ', len);
-			chars_written += len;
+			graph_line_addchars(&line, ' ', len);
 		} else {
-			strbuf_addch(sb, ' ');
-			chars_written++;
+			graph_line_addch(&line, ' ');
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, &line);
 
 	/*
 	 * Update graph->prev_state since we have output a padding line

James Coglan Oct. 14, 2019, 1:01 p.m. UTC | #13

On 14/10/2019 13:55, James Coglan wrote:
> Thanks! For completeness, here is the current state of this patch after I've been through the feedback up to this point:
> 
> From 241180570fbaae04a2263c5ff1ab3b92f54f8004 Mon Sep 17 00:00:00 2001
> From: James Coglan <[e-mail]>
> Date: Thu, 22 Aug 2019 09:30:08 +0100
> Subject: [PATCH] graph: automatically track display width of graph lines
> 
> All the output functions called by `graph_next_line()` currently keep
> track of how many printable chars they've written to the buffer, before
> calling `graph_pad_horizontally()` to pad the line with spaces. Some
> functions do this by incrementing a counter whenever they write to the
> buffer, and others do it by encoding an assumption about how many chars
> are written, as in:
> 
>     graph_pad_horizontally(graph, sb, graph->num_columns * 2);
> 
> This adds a fair amount of noise to the functions' logic and is easily
> broken if one forgets to increment the right counter or update the
> calculations used for padding.
> 
> To make this easier to use, I'm introducing a new struct called
> `graph_line` that wraps a `strbuf` and keeps count of its display width
> implicitly. `graph_next_line()` wraps this around the `struct strbuf *`
> it's given and passes a `struct graph_line *` to the output functions,
> which use its interface.
> 
> The `graph_line` interface wraps the `strbuf_addch()`,
> `strbuf_addchars()` and `strbuf_addstr()` functions, and adds the
> `graph_line_write_column()` function for adding a single character with
> color formatting. The `graph_pad_horizontally()` function can then use
> the `width` field from the struct rather than taking a character count
> as a parameter.
> 
> Signed-off-by: James Coglan <[e-mail]>
> ---
>  graph.c | 194 +++++++++++++++++++++++++++++---------------------------
>  1 file changed, 99 insertions(+), 95 deletions(-)
> 
> diff --git a/graph.c b/graph.c
> index f53135485f..2f81a5d23d 100644
> --- a/graph.c
> +++ b/graph.c
> @@ -112,14 +112,42 @@ static const char *column_get_color_code(unsigned short color)
>  	return column_colors[color];
>  }
>  
> -static void strbuf_write_column(struct strbuf *sb, const struct column *c,
> -				char col_char)
> +struct graph_line {
> +	struct strbuf *buf;
> +	size_t width;
> +};
> +
> +static inline void graph_line_addch(struct graph_line *line, int c)
> +{
> +	strbuf_addch(line->buf, c);
> +	line->width++;
> +}
> +
> +static inline void graph_line_addchars(struct graph_line *line, int c, size_t n)
> +{
> +	strbuf_addchars(line->buf, c, n);
> +	line->width += n;
> +}
> +
> +static inline void graph_line_addstr(struct graph_line *line, const char *s)
> +{
> +	strbuf_addstr(line->buf, s);
> +	line->width += strlen(s);
> +}
> +
> +static inline void graph_line_addcolor(struct graph_line *line, unsigned short color)
> +{
> +	strbuf_addstr(line->buf, column_get_color_code(color));
> +}
> +
> +static void graph_line_write_column(struct graph_line *line, const struct column *c,
> +				    char col_char)
>  {
>  	if (c->color < column_colors_max)
> -		strbuf_addstr(sb, column_get_color_code(c->color));
> -	strbuf_addch(sb, col_char);
> +		graph_line_addcolor(line, c->color);
> +	graph_line_addch(line, col_char);
>  	if (c->color < column_colors_max)
> -		strbuf_addstr(sb, column_get_color_code(column_colors_max));
> +		graph_line_addcolor(line, column_colors_max);
>  }
>  
>  struct git_graph {
> @@ -686,8 +714,7 @@ static int graph_is_mapping_correct(struct git_graph *graph)
>  	return 1;
>  }
>  
> -static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
> -				   int chars_written)
> +static void graph_pad_horizontally(struct git_graph *graph, struct graph_line *line)
>  {
>  	/*
>  	 * Add additional spaces to the end of the strbuf, so that all
> @@ -696,12 +723,12 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
>  	 * This way, fields printed to the right of the graph will remain
>  	 * aligned for the entire commit.
>  	 */
> -	if (chars_written < graph->width)
> -		strbuf_addchars(sb, ' ', graph->width - chars_written);
> +	if (line->width < graph->width)
> +		graph_line_addchars(line, ' ', graph->width - line->width);
>  }
>  
>  static void graph_output_padding_line(struct git_graph *graph,
> -				      struct strbuf *sb)
> +				      struct graph_line *line)
>  {
>  	int i;
>  
> @@ -719,11 +746,11 @@ static void graph_output_padding_line(struct git_graph *graph,
>  	 * Output a padding row, that leaves all branch lines unchanged
>  	 */
>  	for (i = 0; i < graph->num_new_columns; i++) {
> -		strbuf_write_column(sb, &graph->new_columns[i], '|');
> -		strbuf_addch(sb, ' ');
> +		graph_line_write_column(line, &graph->new_columns[i], '|');
> +		graph_line_addch(line, ' ');
>  	}
>  
> -	graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
> +	graph_pad_horizontally(graph, line);
>  }
>  
>  
> @@ -733,14 +760,14 @@ int graph_width(struct git_graph *graph)
>  }
>  
>  
> -static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
> +static void graph_output_skip_line(struct git_graph *graph, struct graph_line *line)
>  {
>  	/*
>  	 * Output an ellipsis to indicate that a portion
>  	 * of the graph is missing.
>  	 */
> -	strbuf_addstr(sb, "...");
> -	graph_pad_horizontally(graph, sb, 3);
> +	graph_line_addstr(line, "...");
> +	graph_pad_horizontally(graph, line);
>  
>  	if (graph->num_parents >= 3 &&
>  	    graph->commit_index < (graph->num_columns - 1))
> @@ -750,11 +777,10 @@ static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
>  }
>  
>  static void graph_output_pre_commit_line(struct git_graph *graph,
> -					 struct strbuf *sb)
> +					 struct graph_line *line)
>  {
>  	int num_expansion_rows;
>  	int i, seen_this;
> -	int chars_written;
>  
>  	/*
>  	 * This function formats a row that increases the space around a commit
> @@ -777,14 +803,12 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>  	 * Output the row
>  	 */
>  	seen_this = 0;
> -	chars_written = 0;
>  	for (i = 0; i < graph->num_columns; i++) {
>  		struct column *col = &graph->columns[i];
>  		if (col->commit == graph->commit) {
>  			seen_this = 1;
> -			strbuf_write_column(sb, col, '|');
> -			strbuf_addchars(sb, ' ', graph->expansion_row);
> -			chars_written += 1 + graph->expansion_row;
> +			graph_line_write_column(line, col, '|');
> +			graph_line_addchars(line, ' ', graph->expansion_row);
>  		} else if (seen_this && (graph->expansion_row == 0)) {
>  			/*
>  			 * This is the first line of the pre-commit output.
> @@ -797,22 +821,18 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>  			 */
>  			if (graph->prev_state == GRAPH_POST_MERGE &&
>  			    graph->prev_commit_index < i)
> -				strbuf_write_column(sb, col, '\\');
> +				graph_line_write_column(line, col, '\\');
>  			else
> -				strbuf_write_column(sb, col, '|');
> -			chars_written++;
> +				graph_line_write_column(line, col, '|');
>  		} else if (seen_this && (graph->expansion_row > 0)) {
> -			strbuf_write_column(sb, col, '\\');
> -			chars_written++;
> +			graph_line_write_column(line, col, '\\');
>  		} else {
> -			strbuf_write_column(sb, col, '|');
> -			chars_written++;
> +			graph_line_write_column(line, col, '|');
>  		}
> -		strbuf_addch(sb, ' ');
> -		chars_written++;
> +		graph_line_addch(line, ' ');
>  	}
>  
> -	graph_pad_horizontally(graph, sb, chars_written);
> +	graph_pad_horizontally(graph, line);
>  
>  	/*
>  	 * Increment graph->expansion_row,
> @@ -823,7 +843,7 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>  		graph_update_state(graph, GRAPH_COMMIT);
>  }
>  
> -static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
> +static void graph_output_commit_char(struct git_graph *graph, struct graph_line *line)
>  {
>  	/*
>  	 * For boundary commits, print 'o'
> @@ -831,22 +851,20 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
>  	 */
>  	if (graph->commit->object.flags & BOUNDARY) {
>  		assert(graph->revs->boundary);
> -		strbuf_addch(sb, 'o');
> +		graph_line_addch(line, 'o');
>  		return;
>  	}
>  
>  	/*
>  	 * get_revision_mark() handles all other cases without assert()
>  	 */
> -	strbuf_addstr(sb, get_revision_mark(graph->revs, graph->commit));
> +	graph_line_addstr(line, get_revision_mark(graph->revs, graph->commit));
>  }
>  
>  /*
> - * Draw the horizontal dashes of an octopus merge and return the number of
> - * characters written.
> + * Draw the horizontal dashes of an octopus merge.
>   */
> -static int graph_draw_octopus_merge(struct git_graph *graph,
> -				    struct strbuf *sb)
> +static void graph_draw_octopus_merge(struct git_graph *graph, struct graph_line *line)
>  {
>  	/*
>  	 * Here dashless_parents represents the number of parents which don't
> @@ -886,17 +904,16 @@ static int graph_draw_octopus_merge(struct git_graph *graph,
>  
>  	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 ? '.' : '-');
> +		graph_line_write_column(line, &graph->new_columns[i+first_col], '-');
> +		graph_line_write_column(line, &graph->new_columns[i+first_col],
> +					  i == dashful_parents-1 ? '.' : '-');
>  	}
> -	return 2 * dashful_parents;
>  }
>  
> -static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
> +static void graph_output_commit_line(struct git_graph *graph, struct graph_line *line)
>  {
>  	int seen_this = 0;
> -	int i, chars_written;
> +	int i;
>  
>  	/*
>  	 * Output the row containing this commit
> @@ -906,7 +923,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  	 * children that we have already processed.)
>  	 */
>  	seen_this = 0;
> -	chars_written = 0;
>  	for (i = 0; i <= graph->num_columns; i++) {
>  		struct column *col = &graph->columns[i];
>  		struct commit *col_commit;
> @@ -920,15 +936,12 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  
>  		if (col_commit == graph->commit) {
>  			seen_this = 1;
> -			graph_output_commit_char(graph, sb);
> -			chars_written++;
> +			graph_output_commit_char(graph, line);
>  
>  			if (graph->num_parents > 2)
> -				chars_written += graph_draw_octopus_merge(graph,
> -									  sb);
> +				graph_draw_octopus_merge(graph, line);
>  		} else if (seen_this && (graph->num_parents > 2)) {
> -			strbuf_write_column(sb, col, '\\');
> -			chars_written++;
> +			graph_line_write_column(line, col, '\\');
>  		} else if (seen_this && (graph->num_parents == 2)) {
>  			/*
>  			 * This is a 2-way merge commit.
> @@ -945,19 +958,16 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  			 */
>  			if (graph->prev_state == GRAPH_POST_MERGE &&
>  			    graph->prev_commit_index < i)
> -				strbuf_write_column(sb, col, '\\');
> +				graph_line_write_column(line, col, '\\');
>  			else
> -				strbuf_write_column(sb, col, '|');
> -			chars_written++;
> +				graph_line_write_column(line, col, '|');
>  		} else {
> -			strbuf_write_column(sb, col, '|');
> -			chars_written++;
> +			graph_line_write_column(line, col, '|');
>  		}
> -		strbuf_addch(sb, ' ');
> -		chars_written++;
> +		graph_line_addch(line, ' ');
>  	}
>  
> -	graph_pad_horizontally(graph, sb, chars_written);
> +	graph_pad_horizontally(graph, line);
>  
>  	/*
>  	 * Update graph->state
> @@ -981,15 +991,14 @@ static struct column *find_new_column_by_commit(struct git_graph *graph,
>  	return NULL;
>  }
>  
> -static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
> +static void graph_output_post_merge_line(struct git_graph *graph, struct graph_line *line)
>  {
>  	int seen_this = 0;
> -	int i, j, chars_written;
> +	int i, j;
>  
>  	/*
>  	 * Output the post-merge row
>  	 */
> -	chars_written = 0;
>  	for (i = 0; i <= graph->num_columns; i++) {
>  		struct column *col = &graph->columns[i];
>  		struct commit *col_commit;
> @@ -1016,29 +1025,25 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
>  			par_column = find_new_column_by_commit(graph, parents->item);
>  			assert(par_column);
>  
> -			strbuf_write_column(sb, par_column, '|');
> -			chars_written++;
> +			graph_line_write_column(line, par_column, '|');
>  			for (j = 0; j < graph->num_parents - 1; j++) {
>  				parents = next_interesting_parent(graph, parents);
>  				assert(parents);
>  				par_column = find_new_column_by_commit(graph, parents->item);
>  				assert(par_column);
> -				strbuf_write_column(sb, par_column, '\\');
> -				strbuf_addch(sb, ' ');
> +				graph_line_write_column(line, par_column, '\\');
> +				graph_line_addch(line, ' ');
>  			}
> -			chars_written += j * 2;
>  		} else if (seen_this) {
> -			strbuf_write_column(sb, col, '\\');
> -			strbuf_addch(sb, ' ');
> -			chars_written += 2;
> +			graph_line_write_column(line, col, '\\');
> +			graph_line_addch(line, ' ');
>  		} else {
> -			strbuf_write_column(sb, col, '|');
> -			strbuf_addch(sb, ' ');
> -			chars_written += 2;
> +			graph_line_write_column(line, col, '|');
> +			graph_line_addch(line, ' ');
>  		}
>  	}
>  
> -	graph_pad_horizontally(graph, sb, chars_written);
> +	graph_pad_horizontally(graph, line);
>  
>  	/*
>  	 * Update graph->state
> @@ -1049,7 +1054,7 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
>  		graph_update_state(graph, GRAPH_COLLAPSING);
>  }
>  
> -static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
> +static void graph_output_collapsing_line(struct git_graph *graph, struct graph_line *line)
>  {
>  	int i;
>  	short used_horizontal = 0;
> @@ -1159,9 +1164,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
>  	for (i = 0; i < graph->mapping_size; i++) {
>  		int target = graph->new_mapping[i];
>  		if (target < 0)
> -			strbuf_addch(sb, ' ');
> +			graph_line_addch(line, ' ');
>  		else if (target * 2 == i)
> -			strbuf_write_column(sb, &graph->new_columns[target], '|');
> +			graph_line_write_column(line, &graph->new_columns[target], '|');
>  		else if (target == horizontal_edge_target &&
>  			 i != horizontal_edge - 1) {
>  				/*
> @@ -1172,16 +1177,16 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
>  				if (i != (target * 2)+3)
>  					graph->new_mapping[i] = -1;
>  				used_horizontal = 1;
> -			strbuf_write_column(sb, &graph->new_columns[target], '_');
> +			graph_line_write_column(line, &graph->new_columns[target], '_');
>  		} else {
>  			if (used_horizontal && i < horizontal_edge)
>  				graph->new_mapping[i] = -1;
> -			strbuf_write_column(sb, &graph->new_columns[target], '/');
> +			graph_line_write_column(line, &graph->new_columns[target], '/');
>  
>  		}
>  	}
>  
> -	graph_pad_horizontally(graph, sb, graph->mapping_size);
> +	graph_pad_horizontally(graph, line);
>  
>  	/*
>  	 * Swap mapping and new_mapping
> @@ -1199,24 +1204,26 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
>  
>  int graph_next_line(struct git_graph *graph, struct strbuf *sb)
>  {
> +	struct graph_line line = { .buf = sb, .width = 0 };
> +
>  	switch (graph->state) {
>  	case GRAPH_PADDING:
> -		graph_output_padding_line(graph, sb);
> +		graph_output_padding_line(graph, &line);
>  		return 0;
>  	case GRAPH_SKIP:
> -		graph_output_skip_line(graph, sb);
> +		graph_output_skip_line(graph, &line);
>  		return 0;
>  	case GRAPH_PRE_COMMIT:
> -		graph_output_pre_commit_line(graph, sb);
> +		graph_output_pre_commit_line(graph, &line);
>  		return 0;
>  	case GRAPH_COMMIT:
> -		graph_output_commit_line(graph, sb);
> +		graph_output_commit_line(graph, &line);
>  		return 1;
>  	case GRAPH_POST_MERGE:
> -		graph_output_post_merge_line(graph, sb);
> +		graph_output_post_merge_line(graph, &line);
>  		return 0;
>  	case GRAPH_COLLAPSING:
> -		graph_output_collapsing_line(graph, sb);
> +		graph_output_collapsing_line(graph, &line);
>  		return 0;
>  	}
>  
> @@ -1227,7 +1234,7 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb)
>  static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
>  {
>  	int i;
> -	int chars_written = 0;
> +	struct graph_line line = { .buf = sb, .width = 0 };
>  
>  	if (graph->state != GRAPH_COMMIT) {
>  		graph_next_line(graph, sb);
> @@ -1244,20 +1251,17 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
>  	for (i = 0; i < graph->num_columns; i++) {
>  		struct column *col = &graph->columns[i];
>  
> -		strbuf_write_column(sb, col, '|');
> -		chars_written++;
> +		graph_line_write_column(&line, col, '|');
>  
>  		if (col->commit == graph->commit && graph->num_parents > 2) {
>  			int len = (graph->num_parents - 2) * 2;
> -			strbuf_addchars(sb, ' ', len);
> -			chars_written += len;
> +			graph_line_addchars(&line, ' ', len);
>  		} else {
> -			strbuf_addch(sb, ' ');
> -			chars_written++;
> +			graph_line_addch(&line, ' ');
>  		}
>  	}
>  
> -	graph_pad_horizontally(graph, sb, chars_written);
> +	graph_pad_horizontally(graph, &line);
>  
>  	/*
>  	 * Update graph->prev_state since we have output a padding line

In addition to this, I'd like to include the following patch that moves the `graph_pad_horizontally()` calls. By the way, what's the best way for me to submit the whole updated patch series after responding to all feedback?

From 97d230c8a8d9b677b331e37482039384589b096a Mon Sep 17 00:00:00 2001
From: James Coglan <[e-mail]>
Date: Mon, 14 Oct 2019 12:10:06 +0100
Subject: [PATCH] graph: handle line padding in `graph_next_line()`

Now that the display width of graph lines is implicitly tracked via the
`graph_line` interface, the calls to `graph_pad_horizontally()` no
longer need to be located inside the individual output functions, where
the character counting was previously being done.

All the functions called by `graph_next_line()` generate a line of
output, then call `graph_pad_horizontally()`, and finally change the
graph state if necessary. As padding is the final change to the output
done by all these functions, it can be removed from all of them and done
in `graph_next_line()` instead.

I've also moved the guard in `graph_output_padding_line()` that checks
the graph has a commit; this function is only called by
`graph_next_line()` and we must not pad the `graph_line` if no commit is
set.
---
 graph.c | 49 ++++++++++++++++++++-----------------------------
 1 file changed, 20 insertions(+), 29 deletions(-)

diff --git a/graph.c b/graph.c
index 2f81a5d23d..4c68557b17 100644
--- a/graph.c
+++ b/graph.c
@@ -732,16 +732,6 @@ static void graph_output_padding_line(struct git_graph *graph,
 {
 	int i;
 
-	/*
-	 * We could conceivable be called with a NULL commit
-	 * if our caller has a bug, and invokes graph_next_line()
-	 * immediately after graph_init(), without first calling
-	 * graph_update().  Return without outputting anything in this
-	 * case.
-	 */
-	if (!graph->commit)
-		return;
-
 	/*
 	 * Output a padding row, that leaves all branch lines unchanged
 	 */
@@ -749,8 +739,6 @@ static void graph_output_padding_line(struct git_graph *graph,
 		graph_line_write_column(line, &graph->new_columns[i], '|');
 		graph_line_addch(line, ' ');
 	}
-
-	graph_pad_horizontally(graph, line);
 }
 
 
@@ -767,7 +755,6 @@ static void graph_output_skip_line(struct git_graph *graph, struct graph_line *l
 	 * of the graph is missing.
 	 */
 	graph_line_addstr(line, "...");
-	graph_pad_horizontally(graph, line);
 
 	if (graph->num_parents >= 3 &&
 	    graph->commit_index < (graph->num_columns - 1))
@@ -832,8 +819,6 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		graph_line_addch(line, ' ');
 	}
 
-	graph_pad_horizontally(graph, line);
-
 	/*
 	 * Increment graph->expansion_row,
 	 * and move to state GRAPH_COMMIT if necessary
@@ -967,8 +952,6 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
 		graph_line_addch(line, ' ');
 	}
 
-	graph_pad_horizontally(graph, line);
-
 	/*
 	 * Update graph->state
 	 */
@@ -1043,8 +1026,6 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 		}
 	}
 
-	graph_pad_horizontally(graph, line);
-
 	/*
 	 * Update graph->state
 	 */
@@ -1186,8 +1167,6 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 		}
 	}
 
-	graph_pad_horizontally(graph, line);
-
 	/*
 	 * Swap mapping and new_mapping
 	 */
@@ -1204,31 +1183,43 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
 
 int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 {
+	int shown_commit_line = 0;
 	struct graph_line line = { .buf = sb, .width = 0 };
 
+	/*
+	 * We could conceivable be called with a NULL commit
+	 * if our caller has a bug, and invokes graph_next_line()
+	 * immediately after graph_init(), without first calling
+	 * graph_update().  Return without outputting anything in this
+	 * case.
+	 */
+	if (!graph->commit)
+		return -1;
+
 	switch (graph->state) {
 	case GRAPH_PADDING:
 		graph_output_padding_line(graph, &line);
-		return 0;
+		break;
 	case GRAPH_SKIP:
 		graph_output_skip_line(graph, &line);
-		return 0;
+		break;
 	case GRAPH_PRE_COMMIT:
 		graph_output_pre_commit_line(graph, &line);
-		return 0;
+		break;
 	case GRAPH_COMMIT:
 		graph_output_commit_line(graph, &line);
-		return 1;
+		shown_commit_line = 1;
+		break;
 	case GRAPH_POST_MERGE:
 		graph_output_post_merge_line(graph, &line);
-		return 0;
+		break;
 	case GRAPH_COLLAPSING:
 		graph_output_collapsing_line(graph, &line);
-		return 0;
+		break;
 	}
 
-	assert(0);
-	return 0;
+	graph_pad_horizontally(graph, &line);
+	return shown_commit_line;
 }
 
 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)

Junio C Hamano Oct. 16, 2019, 2:15 a.m. UTC | #14

James Coglan <[e-mail]> writes:

>> Is there a reason why you need a pointer to a strbuf that is
>> allocated separately?  E.g. would it make it harder to manage
>> if the above were
>> 
>> 	struct graphbuf {
>> 		struct strbuf buf;
>> 		int width; /* display width in columns */
>> 	};
>> 
>> which is essentially what Dscho suggested?
>
> I used a pointer here because I create the wrapper struct in
> `graph_next_line()`, which is an external interface that takes a
> `struct strbuf *`:
>
> int graph_next_line(struct git_graph *graph, struct strbuf *sb)
> {
> 	struct graph_line line = { .buf = sb, .width = 0 };
> 	// ...
> }
>
> So I'm not allocating the strbuf here, just wrapping a pointer to
> it.

OK, so existing callers allocate strbuf, and you are merely adding a
wrapper structure to keep track of the width.  The management of the
lifetime of the strbuf is not your business so there is no reason to
inline the structure in graph_line.  Makes sense.  Thanks.

Patch

diff --git a/graph.c b/graph.c
index f53135485f..c56fdec1fc 100644
--- a/graph.c
+++ b/graph.c
@@ -115,11 +115,20 @@  static const char *column_get_color_code(unsigned short color)
 static void strbuf_write_column(struct strbuf *sb, const struct column *c,
 				char col_char)
 {
+	/*
+	 * Remember the buffer's width as we're about to add non-printing
+	 * content to it, and we want to avoid counting the byte length
+	 * of this content towards the buffer's visible width
+	 */
+	size_t prev_width = sb->width;
+
 	if (c->color < column_colors_max)
 		strbuf_addstr(sb, column_get_color_code(c->color));
 	strbuf_addch(sb, col_char);
 	if (c->color < column_colors_max)
 		strbuf_addstr(sb, column_get_color_code(column_colors_max));
+
+	sb->width = prev_width + 1;
 }
 
 struct git_graph {
@@ -686,8 +695,7 @@  static int graph_is_mapping_correct(struct git_graph *graph)
 	return 1;
 }
 
-static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
-				   int chars_written)
+static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)
 {
 	/*
 	 * Add additional spaces to the end of the strbuf, so that all
@@ -696,8 +704,8 @@  static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
 	 * This way, fields printed to the right of the graph will remain
 	 * aligned for the entire commit.
 	 */
-	if (chars_written < graph->width)
-		strbuf_addchars(sb, ' ', graph->width - chars_written);
+	if (sb->width < graph->width)
+		strbuf_addchars(sb, ' ', graph->width - sb->width);
 }
 
 static void graph_output_padding_line(struct git_graph *graph,
@@ -723,7 +731,7 @@  static void graph_output_padding_line(struct git_graph *graph,
 		strbuf_addch(sb, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
+	graph_pad_horizontally(graph, sb);
 }
 
 
@@ -740,7 +748,7 @@  static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
 	 * of the graph is missing.
 	 */
 	strbuf_addstr(sb, "...");
-	graph_pad_horizontally(graph, sb, 3);
+	graph_pad_horizontally(graph, sb);
 
 	if (graph->num_parents >= 3 &&
 	    graph->commit_index < (graph->num_columns - 1))
@@ -754,7 +762,6 @@  static void graph_output_pre_commit_line(struct git_graph *graph,
 {
 	int num_expansion_rows;
 	int i, seen_this;
-	int chars_written;
 
 	/*
 	 * This function formats a row that increases the space around a commit
@@ -777,14 +784,12 @@  static void graph_output_pre_commit_line(struct git_graph *graph,
 	 * Output the row
 	 */
 	seen_this = 0;
-	chars_written = 0;
 	for (i = 0; i < graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		if (col->commit == graph->commit) {
 			seen_this = 1;
 			strbuf_write_column(sb, col, '|');
 			strbuf_addchars(sb, ' ', graph->expansion_row);
-			chars_written += 1 + graph->expansion_row;
 		} else if (seen_this && (graph->expansion_row == 0)) {
 			/*
 			 * This is the first line of the pre-commit output.
@@ -800,19 +805,15 @@  static void graph_output_pre_commit_line(struct git_graph *graph,
 				strbuf_write_column(sb, col, '\\');
 			else
 				strbuf_write_column(sb, col, '|');
-			chars_written++;
 		} else if (seen_this && (graph->expansion_row > 0)) {
 			strbuf_write_column(sb, col, '\\');
-			chars_written++;
 		} else {
 			strbuf_write_column(sb, col, '|');
-			chars_written++;
 		}
 		strbuf_addch(sb, ' ');
-		chars_written++;
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, sb);
 
 	/*
 	 * Increment graph->expansion_row,
@@ -842,11 +843,9 @@  static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 }
 
 /*
- * Draw the horizontal dashes of an octopus merge and return the number of
- * characters written.
+ * Draw the horizontal dashes of an octopus merge.
  */
-static int graph_draw_octopus_merge(struct git_graph *graph,
-				    struct strbuf *sb)
+static void graph_draw_octopus_merge(struct git_graph *graph, struct strbuf *sb)
 {
 	/*
 	 * Here dashless_parents represents the number of parents which don't
@@ -890,13 +889,12 @@  static int graph_draw_octopus_merge(struct git_graph *graph,
 		strbuf_write_column(sb, &graph->new_columns[i+first_col],
 				    i == dashful_parents-1 ? '.' : '-');
 	}
-	return 2 * dashful_parents;
 }
 
 static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
-	int i, chars_written;
+	int i;
 
 	/*
 	 * Output the row containing this commit
@@ -906,7 +904,6 @@  static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 	 * children that we have already processed.)
 	 */
 	seen_this = 0;
-	chars_written = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
@@ -921,14 +918,11 @@  static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 		if (col_commit == graph->commit) {
 			seen_this = 1;
 			graph_output_commit_char(graph, sb);
-			chars_written++;
 
 			if (graph->num_parents > 2)
-				chars_written += graph_draw_octopus_merge(graph,
-									  sb);
+				graph_draw_octopus_merge(graph, sb);
 		} else if (seen_this && (graph->num_parents > 2)) {
 			strbuf_write_column(sb, col, '\\');
-			chars_written++;
 		} else if (seen_this && (graph->num_parents == 2)) {
 			/*
 			 * This is a 2-way merge commit.
@@ -948,16 +942,13 @@  static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 				strbuf_write_column(sb, col, '\\');
 			else
 				strbuf_write_column(sb, col, '|');
-			chars_written++;
 		} else {
 			strbuf_write_column(sb, col, '|');
-			chars_written++;
 		}
 		strbuf_addch(sb, ' ');
-		chars_written++;
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, sb);
 
 	/*
 	 * Update graph->state
@@ -984,12 +975,11 @@  static struct column *find_new_column_by_commit(struct git_graph *graph,
 static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
-	int i, j, chars_written;
+	int i, j;
 
 	/*
 	 * Output the post-merge row
 	 */
-	chars_written = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
@@ -1017,7 +1007,6 @@  static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 			assert(par_column);
 
 			strbuf_write_column(sb, par_column, '|');
-			chars_written++;
 			for (j = 0; j < graph->num_parents - 1; j++) {
 				parents = next_interesting_parent(graph, parents);
 				assert(parents);
@@ -1026,19 +1015,16 @@  static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 				strbuf_write_column(sb, par_column, '\\');
 				strbuf_addch(sb, ' ');
 			}
-			chars_written += j * 2;
 		} else if (seen_this) {
 			strbuf_write_column(sb, col, '\\');
 			strbuf_addch(sb, ' ');
-			chars_written += 2;
 		} else {
 			strbuf_write_column(sb, col, '|');
 			strbuf_addch(sb, ' ');
-			chars_written += 2;
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, sb);
 
 	/*
 	 * Update graph->state
@@ -1181,7 +1167,7 @@  static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, graph->mapping_size);
+	graph_pad_horizontally(graph, sb);
 
 	/*
 	 * Swap mapping and new_mapping
@@ -1199,6 +1185,8 @@  static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 
 int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 {
+	sb->width = 0;
+
 	switch (graph->state) {
 	case GRAPH_PADDING:
 		graph_output_padding_line(graph, sb);
@@ -1227,7 +1215,6 @@  int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int i;
-	int chars_written = 0;
 
 	if (graph->state != GRAPH_COMMIT) {
 		graph_next_line(graph, sb);
@@ -1245,19 +1232,16 @@  static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 		struct column *col = &graph->columns[i];
 
 		strbuf_write_column(sb, col, '|');
-		chars_written++;
 
 		if (col->commit == graph->commit && graph->num_parents > 2) {
 			int len = (graph->num_parents - 2) * 2;
 			strbuf_addchars(sb, ' ', len);
-			chars_written += len;
 		} else {
 			strbuf_addch(sb, ' ');
-			chars_written++;
 		}
 	}
 
-	graph_pad_horizontally(graph, sb, chars_written);
+	graph_pad_horizontally(graph, sb);
 
 	/*
 	 * Update graph->prev_state since we have output a padding line
diff --git a/strbuf.h b/strbuf.h
index f62278a0be..3a98147321 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -66,11 +66,12 @@  struct string_list;
 struct strbuf {
 	size_t alloc;
 	size_t len;
+	size_t width;
 	char *buf;
 };
 
 extern char strbuf_slopbuf[];
-#define STRBUF_INIT  { .alloc = 0, .len = 0, .buf = strbuf_slopbuf }
+#define STRBUF_INIT  { .alloc = 0, .len = 0, .width = 0, .buf = strbuf_slopbuf }
 
 /*
  * Predeclare this here, since cache.h includes this file before it defines the
@@ -161,6 +162,10 @@  static inline void strbuf_setlen(struct strbuf *sb, size_t len)
 {
 	if (len > (sb->alloc ? sb->alloc - 1 : 0))
 		die("BUG: strbuf_setlen() beyond buffer");
+	if (len > sb->len)
+		sb->width += len - sb->len;
+	else
+		sb->width = len;
 	sb->len = len;
 	if (sb->buf != strbuf_slopbuf)
 		sb->buf[len] = '\0';
@@ -231,6 +236,7 @@  static inline void strbuf_addch(struct strbuf *sb, int c)
 		strbuf_grow(sb, 1);
 	sb->buf[sb->len++] = c;
 	sb->buf[sb->len] = '\0';
+	sb->width++;
 }
 
 /**