[RFC/PATCH] graph API: Use horizontal lines for more compact graphs

[RFC/PATCH] graph API: Use horizontal lines for more compact graphs

[Allan Caffee]

Use horizontal lines instead of long diagonal during graph collapsing
and precommit for more compact and legible graphs.

Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
---
 graph.c        |   57 +++++++++++++++++++++++++++++++++++++++++--------------
 t/t4202-log.sh |    6 +---
 2 files changed, 44 insertions(+), 19 deletions(-)

diff --git a/graph.c b/graph.c
index d4571cf..597e545 100644
--- a/graph.c
+++ b/graph.c
@@ -47,20 +47,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
  * - Limit the number of columns, similar to the way gitk does.
  *   If we reach more than a specified number of columns, omit
  *   sections of some columns.
- *
- * - The output during the GRAPH_PRE_COMMIT and GRAPH_COLLAPSING states
- *   could be made more compact by printing horizontal lines, instead of
- *   long diagonal lines.  For example, during collapsing, something like
- *   this:          instead of this:
- *   | | | | |      | | | | |
- *   | |_|_|/       | | | |/
- *   |/| | |        | | |/|
- *   | | | |        | |/| |
- *                  |/| | |
- *                  | | | |
- *
- *   If there are several parallel diagonal lines, they will need to be
- *   replaced with horizontal lines on subsequent rows.
  */
 
 struct column {
@@ -982,6 +968,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 {
 	int i;
 	int *tmp_mapping;
+	short used_horizontal = 0;
+	int horizontal_edge = -1;
+	int horizontal_edge_target = -1;
 
 	/*
 	 * Clear out the new_mapping array
@@ -1019,6 +1008,17 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			 * Move to the left by one
 			 */
 			graph->new_mapping[i - 1] = target;
+			/*
+			 * If there isn't already an edge moving horizontally
+			 * select this one.
+			 */
+			if (horizontal_edge == -1) {
+				int j;
+				horizontal_edge = i;
+				horizontal_edge_target = target;
+				for (j = (target * 2)+3; j < (i - 2); j += 2)
+					graph->new_mapping[j] = target;
+			}
 		} else if (graph->new_mapping[i - 1] == target) {
 			/*
 			 * There is a branch line to our left
@@ -1039,10 +1039,21 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			 *
 			 * The space just to the left of this
 			 * branch should always be empty.
+			 *
+			 * The branch to the left of that space
+			 * should be our eventual target.
 			 */
 			assert(graph->new_mapping[i - 1] > target);
 			assert(graph->new_mapping[i - 2] < 0);
+			assert(graph->new_mapping[i - 3] == target);
 			graph->new_mapping[i - 2] = target;
+			/*
+			 * Mark this branch as the horizontal edge to
+			 * prevent any other edges from moving
+			 * horizontally.
+			 */
+			if (horizontal_edge == -1)
+				horizontal_edge = i;
 		}
 	}
 
@@ -1061,8 +1072,24 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
 			strbuf_write_column(sb, &graph->new_columns[target], '|');
-		else
+		else if (target == horizontal_edge_target &&
+			 i != horizontal_edge - 1) {
+				/*
+				 * Set the mappings for all but the
+				 * first segment to -1 so that they
+				 * won't continue into the next line.
+				 */
+				if (i != (target * 2)+3)
+					graph->new_mapping[i] = -1;
+				used_horizontal = 1;
+			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_pad_horizontally(graph, sb, graph->mapping_size);
diff --git a/t/t4202-log.sh b/t/t4202-log.sh
index b986190..a3b0cb8 100755
--- a/t/t4202-log.sh
+++ b/t/t4202-log.sh
@@ -298,14 +298,12 @@ cat > expect <<\EOF
 * | | |   Merge branch 'side'
 |\ \ \ \
 | * | | | side-2
-| | | |/
-| | |/|
+| | |_|/
 | |/| |
 | * | | side-1
 * | | | Second
 * | | | sixth
-| | |/
-| |/|
+| |_|/
 |/| |
 * | | fifth
 * | | fourth
-- 
1.5.6.3

Re: [RFC/PATCH] graph API: Use horizontal lines for more compact graphs

[Johannes Schindelin]

Hi,

On Mon, 20 Apr 2009, Allan Caffee wrote:

> diff --git a/graph.c b/graph.c
> index d4571cf..597e545 100644
> --- a/graph.c
> +++ b/graph.c
> @@ -47,20 +47,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
>   * - Limit the number of columns, similar to the way gitk does.
>   *   If we reach more than a specified number of columns, omit
>   *   sections of some columns.
> - *
> - * - The output during the GRAPH_PRE_COMMIT and GRAPH_COLLAPSING states
> - *   could be made more compact by printing horizontal lines, instead of
> - *   long diagonal lines.  For example, during collapsing, something like
> - *   this:          instead of this:
> - *   | | | | |      | | | | |
> - *   | |_|_|/       | | | |/
> - *   |/| | |        | | |/|
> - *   | | | |        | |/| |
> - *                  |/| | |
> - *                  | | | |
> - *
> - *   If there are several parallel diagonal lines, they will need to be
> - *   replaced with horizontal lines on subsequent rows.

I like it!

> +				for (j = (target * 2)+3; j < (i - 2); j += 2)

This (target*2)+3 is a bit too magical for me to understand.  But maybe I 
am just too tired?

Ciao,
Dscho

Re: [RFC/PATCH] graph API: Use horizontal lines for more compact graphs

[Allan Caffee]

On Mon, Apr 20, 2009 at 8:56 PM, Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
> Hi,
>
> On Mon, 20 Apr 2009, Allan Caffee wrote:
>
>> diff --git a/graph.c b/graph.c
>> index d4571cf..597e545 100644
>> --- a/graph.c
>> +++ b/graph.c
>> @@ -47,20 +47,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
>>   * - Limit the number of columns, similar to the way gitk does.
>>   *   If we reach more than a specified number of columns, omit
>>   *   sections of some columns.
>> - *
>> - * - The output during the GRAPH_PRE_COMMIT and GRAPH_COLLAPSING states
>> - *   could be made more compact by printing horizontal lines, instead of
>> - *   long diagonal lines.  For example, during collapsing, something like
>> - *   this:          instead of this:
>> - *   | | | | |      | | | | |
>> - *   | |_|_|/       | | | |/
>> - *   |/| | |        | | |/|
>> - *   | | | |        | |/| |
>> - *                  |/| | |
>> - *                  | | | |
>> - *
>> - *   If there are several parallel diagonal lines, they will need to be
>> - *   replaced with horizontal lines on subsequent rows.
>
> I like it!

:) Good!

>> +                             for (j = (target * 2)+3; j < (i - 2); j += 2)
>
> This (target*2)+3 is a bit too magical for me to understand.  But maybe I
> am just too tired?

It is a little magical.  Here target is an index into
graph->new_columns so we double that to get the actual location of the
edge in the string for this line.  So if we take the example that was
in the original TODO:

t(c)
|  t(c) + 3 (i.e. the first horizontal edge)
|  |
v..v    c
| | | | |
| |_|_|/
|/| | |
| | | |

Where c is the "horizontal_edge", t(c) is the target of the
"horizontal_edge" and t(c) + 3 is the location of the first horizontal
segment.  And then of course the += 2 is because we don't want to
change the mappings of the existing vertical edges.  This could really
probably use a comment (suggestions welcome).

Hope that clears things up,
~Allan

Re: [RFC/PATCH] graph API: Use horizontal lines for more compact graphs

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 761 bytes --]

Hi,

On Mon, 20 Apr 2009, Allan Caffee wrote:

> On Mon, Apr 20, 2009 at 8:56 PM, Johannes Schindelin
> <Johannes.Schindelin@gmx.de> wrote:
>
> > On Mon, 20 Apr 2009, Allan Caffee wrote:
> >
> >> +                             for (j = (target * 2)+3; j < (i - 2); j += 2)
> >
> > This (target*2)+3 is a bit too magical for me to understand.  But 
> > maybe I am just too tired?
> 
> It is a little magical.  Here target is an index into
> graph->new_columns so we double that to get the actual location of the
> edge in the string for this line.

Ah.  So how about
				 /*
				  * The variable target is the index of the graph
				  * column, and therefore target*2+3 is the actual
				  * screen column of the first horizontal line.
				  */

Hmm?

Ciao,
Dscho

[RFC/PATCH v2] graph API: Use horizontal lines for more compact graphs

[Allan Caffee]

Use horizontal lines instead of long diagonal during graph collapsing
and precommit for more compact and legible graphs.

Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
---
 graph.c        |   63 ++++++++++++++++++++++++++++++++++++++++++-------------
 t/t4202-log.sh |    6 +---
 2 files changed, 50 insertions(+), 19 deletions(-)

On Tue, 21 Apr 2009, Johannes Schindelin wrote:
> Hi,
> 
> On Mon, 20 Apr 2009, Allan Caffee wrote:
> 
> > On Mon, Apr 20, 2009 at 8:56 PM, Johannes Schindelin
> > <Johannes.Schindelin@gmx.de> wrote:
> >
> > > On Mon, 20 Apr 2009, Allan Caffee wrote:
> > >
> > >> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? for (j = (target * 2)+3; j < (i - 2); j += 2)
> > >
> > > This (target*2)+3 is a bit too magical for me to understand. ?But 
> > > maybe I am just too tired?
> > 
> > It is a little magical.  Here target is an index into
> > graph->new_columns so we double that to get the actual location of the
> > edge in the string for this line.
> 
> Ah.  So how about
> 				 /*
> 				  * The variable target is the index of the graph
> 				  * column, and therefore target*2+3 is the actual
> 				  * screen column of the first horizontal line.
> 				  */

Sounds good to me.  Everything else look good?  

Actually now that I look at it, it might be a good idea to put an assert
statement in that for loop like `assert(graph->new_mapping[j] < 0)' to
make sure we don't clobber any existing lines.  But that seems like
overkill since we're already assured to be the first collapsing edge at
that point, which would imply that all previous odd indeces are empty.
WDYT?

diff --git a/graph.c b/graph.c
index d4571cf..86577b4 100644
--- a/graph.c
+++ b/graph.c
@@ -47,20 +47,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
  * - Limit the number of columns, similar to the way gitk does.
  *   If we reach more than a specified number of columns, omit
  *   sections of some columns.
- *
- * - The output during the GRAPH_PRE_COMMIT and GRAPH_COLLAPSING states
- *   could be made more compact by printing horizontal lines, instead of
- *   long diagonal lines.  For example, during collapsing, something like
- *   this:          instead of this:
- *   | | | | |      | | | | |
- *   | |_|_|/       | | | |/
- *   |/| | |        | | |/|
- *   | | | |        | |/| |
- *                  |/| | |
- *                  | | | |
- *
- *   If there are several parallel diagonal lines, they will need to be
- *   replaced with horizontal lines on subsequent rows.
  */
 
 struct column {
@@ -982,6 +968,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 {
 	int i;
 	int *tmp_mapping;
+	short used_horizontal = 0;
+	int horizontal_edge = -1;
+	int horizontal_edge_target = -1;
 
 	/*
 	 * Clear out the new_mapping array
@@ -1019,6 +1008,23 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			 * Move to the left by one
 			 */
 			graph->new_mapping[i - 1] = target;
+			/*
+			 * If there isn't already an edge moving horizontally
+			 * select this one.
+			 */
+			if (horizontal_edge == -1) {
+				int j;
+				horizontal_edge = i;
+				horizontal_edge_target = target;
+				/*
+				 * The variable target is the index of the graph
+				 * column, and therefore target*2+3 is the
+				 * actual screen column of the first horizontal
+				 * line.
+				 */
+				for (j = (target * 2)+3; j < (i - 2); j += 2)
+					graph->new_mapping[j] = target;
+			}
 		} else if (graph->new_mapping[i - 1] == target) {
 			/*
 			 * There is a branch line to our left
@@ -1039,10 +1045,21 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			 *
 			 * The space just to the left of this
 			 * branch should always be empty.
+			 *
+			 * The branch to the left of that space
+			 * should be our eventual target.
 			 */
 			assert(graph->new_mapping[i - 1] > target);
 			assert(graph->new_mapping[i - 2] < 0);
+			assert(graph->new_mapping[i - 3] == target);
 			graph->new_mapping[i - 2] = target;
+			/*
+			 * Mark this branch as the horizontal edge to
+			 * prevent any other edges from moving
+			 * horizontally.
+			 */
+			if (horizontal_edge == -1)
+				horizontal_edge = i;
 		}
 	}
 
@@ -1061,8 +1078,24 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
 			strbuf_write_column(sb, &graph->new_columns[target], '|');
-		else
+		else if (target == horizontal_edge_target &&
+			 i != horizontal_edge - 1) {
+				/*
+				 * Set the mappings for all but the
+				 * first segment to -1 so that they
+				 * won't continue into the next line.
+				 */
+				if (i != (target * 2)+3)
+					graph->new_mapping[i] = -1;
+				used_horizontal = 1;
+			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_pad_horizontally(graph, sb, graph->mapping_size);
diff --git a/t/t4202-log.sh b/t/t4202-log.sh
index b986190..a3b0cb8 100755
--- a/t/t4202-log.sh
+++ b/t/t4202-log.sh
@@ -298,14 +298,12 @@ cat > expect <<\EOF
 * | | |   Merge branch 'side'
 |\ \ \ \
 | * | | | side-2
-| | | |/
-| | |/|
+| | |_|/
 | |/| |
 | * | | side-1
 * | | | Second
 * | | | sixth
-| | |/
-| |/|
+| |_|/
 |/| |
 * | | fifth
 * | | fourth
-- 
1.5.6.3

Re: [RFC/PATCH v2] graph API: Use horizontal lines for more compact graphs

[Johannes Schindelin]

Hi,

> Everything else look good?

No objection from my side.

> Actually now that I look at it, it might be a good idea to put an assert
> statement in that for loop like `assert(graph->new_mapping[j] < 0)' to
> make sure we don't clobber any existing lines.  But that seems like
> overkill since we're already assured to be the first collapsing edge at
> that point, which would imply that all previous odd indeces are empty.
> WDYT?

Yep, sounds like overkill to me, too.

Thanks!
Dscho

Bug in colored "log --graph" implementation

[Teemu Likonen]

The colored log graph implementation (commit 427fc5b) introduces an
alignment bug which looks like this:


| | * | edf2e37 git-apply: work from subdirectory.
| | * | 4ca0660 working from subdirectory: preparation
| |  | |        
| |   \ \       
| |    \ \      
| |     \ \     
| |      \ \    
| |       \ \   
| *-----. \ \   5401f30 Merge branches 'jc/apply', 'lt/ls-tree', [...]
| |\ \ \ \ \ \  
| | | | | * | | 0501c24 Tutorial: adjust merge example to recursive [...]


In other words, the diagonal lines after this octopus merge are aligned
wrong. To see it yourself type

    git log --graph --oneline a957207

in the Git repository and scroll the output down a bit. Note that the
bug exists with both --color _and_ --no-color.

[PATCH] graph API: fix extra space during pre_commit_line state

[Allan Caffee]

An extra space is being inserted between the "commit" column and all of
the successive edges.  Remove this space.  This regression was
introduced by 427fc5b.

Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
---
 graph.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

On Tue, 21 Apr 2009, Teemu Likonen wrote:
> The colored log graph implementation (commit 427fc5b) introduces an
> alignment bug which looks like this:
> 
> | | * | edf2e37 git-apply: work from subdirectory.
> | | * | 4ca0660 working from subdirectory: preparation
> | |  | |        
> | |   \ \       
> | |    \ \      
> | |     \ \     
> | |      \ \    
> | |       \ \   
> | *-----. \ \   5401f30 Merge branches 'jc/apply', 'lt/ls-tree', [...]
> | |\ \ \ \ \ \  
> | | | | | * | | 0501c24 Tutorial: adjust merge example to recursive [...]
> 
> 
> In other words, the diagonal lines after this octopus merge are aligned
> wrong. To see it yourself type
> 
>     git log --graph --oneline a957207
> 
> in the Git repository and scroll the output down a bit. Note that the
> bug exists with both --color _and_ --no-color.

It's actually the lines before the merge that are shifted to the right
by one.  This patch should fix that.

This issue exposes a gap in the existing test coverage, which doesn't
exercise the pre_commit_line code.  Maybe another patch is in order to
extend t4202-log to cover pre-commit lines and octopus merges.

diff --git a/graph.c b/graph.c
index d4571cf..31e09eb 100644
--- a/graph.c
+++ b/graph.c
@@ -727,8 +727,8 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		if (col->commit == graph->commit) {
 			seen_this = 1;
 			strbuf_write_column(sb, col, '|');
-			strbuf_addf(sb, " %*s", graph->expansion_row, "");
-			chars_written += 2 + graph->expansion_row;
+			strbuf_addf(sb, "%*s", 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.
-- 
1.5.6.3

Re: [PATCH] graph API: fix extra space during pre_commit_line state

[Teemu Likonen]

On 2009-04-21 14:34 (-0400), Allan Caffee wrote:

> An extra space is being inserted between the "commit" column and all of
> the successive edges.  Remove this space.  This regression was
> introduced by 427fc5b.
>
> Signed-off-by: Allan Caffee <allan.caffee@gmail.com>

Looks like it's working now, thanks. Let's Cc to Junio so that he
doesn't miss the fix.

> This issue exposes a gap in the existing test coverage, which doesn't
> exercise the pre_commit_line code.  Maybe another patch is in order to
> extend t4202-log to cover pre-commit lines and octopus merges.

I think that's a good idea. I like "log --graph" very much and when
someone alters that part of the code I run my own visual "test suites"
to notice if my pet feature has been broken. :-) Automatic tests would
be helpful.

Re: [PATCH] graph API: fix extra space during pre_commit_line state

[Allan Caffee]

On Wed, 22 Apr 2009, Teemu Likonen wrote:

> On 2009-04-21 14:34 (-0400), Allan Caffee wrote:
> 
> > An extra space is being inserted between the "commit" column and all of
> > the successive edges.  Remove this space.  This regression was
> > introduced by 427fc5b.
> >
> > Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
> 
> Looks like it's working now, thanks. Let's Cc to Junio so that he
> doesn't miss the fix.

Actually, Junio, please disregard this patch for the moment.  I'll
resend it in a series along with another minor fix related to octopus
merges.

> > This issue exposes a gap in the existing test coverage, which doesn't
> > exercise the pre_commit_line code.  Maybe another patch is in order to
> > extend t4202-log to cover pre-commit lines and octopus merges.
> 
> I think that's a good idea. I like "log --graph" very much and when
> someone alters that part of the code I run my own visual "test suites"
> to notice if my pet feature has been broken. :-) Automatic tests would
> be helpful.

I'll include a test patch in that series as well.

[PATCH 2/3] graph API: fix extra space during pre_commit_line state

[Allan Caffee]

An extra space is being inserted between the "commit" column and all of
the successive edges.  Remove this space.  This regression was
introduced by 427fc5b.

Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
---
 graph.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/graph.c b/graph.c
index d4571cf..31e09eb 100644
--- a/graph.c
+++ b/graph.c
@@ -727,8 +727,8 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		if (col->commit == graph->commit) {
 			seen_this = 1;
 			strbuf_write_column(sb, col, '|');
-			strbuf_addf(sb, " %*s", graph->expansion_row, "");
-			chars_written += 2 + graph->expansion_row;
+			strbuf_addf(sb, "%*s", 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.
-- 
1.5.6.3

[PATCH 1/3] t4202-log: extend test coverage of graphing

[Allan Caffee]

Extend this test to cover the rendering of graphs with octopus merges
and pre_commit lines.

Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
---
 t/t4202-log.sh |   28 +++++++++++++++++++++++++++-
 1 files changed, 27 insertions(+), 1 deletions(-)

This patch by itself should cause the test to fail.  Proving that the
following two patches are required too return us to sane behaviour.

diff --git a/t/t4202-log.sh b/t/t4202-log.sh
index b986190..64502e2 100755
--- a/t/t4202-log.sh
+++ b/t/t4202-log.sh
@@ -284,10 +284,36 @@ test_expect_success 'set up more tangled history' '
 	git merge master~3 &&
 	git merge side~1 &&
 	git checkout master &&
-	git merge tangle
+	git merge tangle &&
+	git checkout -b reach &&
+	test_commit reach &&
+	git checkout master &&
+	git checkout -b octopus-a &&
+	test_commit octopus-a &&
+	git checkout master &&
+	git checkout -b octopus-b &&
+	test_commit octopus-b &&
+	git checkout master &&
+	test_commit seventh &&
+	git merge octopus-a octopus-b
+	git merge reach
 '
 
 cat > expect <<\EOF
+*   Merge branch 'reach'
+|\
+| \
+|  \
+*-. \   Merge branches 'octopus-a' and 'octopus-b'
+|\ \ \
+* | | | seventh
+| | * | octopus-b
+| |/ /
+|/| |
+| * | octopus-a
+|/ /
+| * reach
+|/
 *   Merge branch 'tangle'
 |\
 | *   Merge branch 'side' (early part) into tangle
-- 
1.5.6.3

[PATCH 2/3] graph API: fix extra space during pre_commit_line state

[Allan Caffee]

An extra space is being inserted between the "commit" column and all of
the successive edges.  Remove this space.  This regression was
introduced by 427fc5b.

Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
---
 graph.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/graph.c b/graph.c
index d4571cf..31e09eb 100644
--- a/graph.c
+++ b/graph.c
@@ -727,8 +727,8 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		if (col->commit == graph->commit) {
 			seen_this = 1;
 			strbuf_write_column(sb, col, '|');
-			strbuf_addf(sb, " %*s", graph->expansion_row, "");
-			chars_written += 2 + graph->expansion_row;
+			strbuf_addf(sb, "%*s", 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.
-- 
1.5.6.3

[PATCH 3/3] graph API: fix a bug in the rendering of octopus merges

[Allan Caffee]

An off by one error was causing octopus merges with 3 parents to not be
rendered correctly.  This regression was introduced by 427fc5.

Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
---
 graph.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/graph.c b/graph.c
index 31e09eb..b7879f8 100644
--- a/graph.c
+++ b/graph.c
@@ -852,7 +852,7 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 			graph_output_commit_char(graph, sb);
 			chars_written++;
 
-			if (graph->num_parents > 3)
+			if (graph->num_parents > 2)
 				chars_written += graph_draw_octopus_merge(graph,
 									  sb);
 		} else if (seen_this && (graph->num_parents > 2)) {
-- 
1.5.6.3

Re: [RFC/PATCH v2] graph API: Use horizontal lines for more compact graphs

[Allan Caffee]

On Tue, 21 Apr 2009, Allan Caffee wrote:

> Use horizontal lines instead of long diagonal during graph collapsing
> and precommit for more compact and legible graphs.

Please replace this message with:
----8<----------------
Use horizontal lines instead of long diagonal lines during the
collapsing state of graph rendering.  For example what used to be:

 | | | | |
 | | | |/
 | | |/|
 | |/| |
 |/| | |
 | | | |
is now
 | | | | |
 | |_|_|/
 |/| | |
 | | | |

This results in more compact and legible graphs.
---->8----------------

Notice that I dropped out the part about precommits.  Originally I
intended to utilize horizontal lines in pre_commit_line's as well.  But
partway through I decided to just do collapsing_line's for now since (a)
collapsing_line edges tend to extend much longer and (b)
pre_commit_line's are less common since they only occur when there is a
merge with at least three parents, and (c) the change for
pre_commit_lines is liable to be more complicated and error-prone.

[PATCH v2 (resend)] graph API: Use horizontal lines for more compact graphs

[Allan Caffee]

Use horizontal lines instead of long diagonal lines during the
collapsing state of graph rendering.  For example what used to be:

 | | | | |
 | | | |/
 | | |/|
 | |/| |
 |/| | |
 | | | |
is now
 | | | | |
 | |_|_|/
 |/| | |
 | | | |

resulting in more compact and legible graphs.

Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
---

Junio, is this patch acceptable for inclusion?

 graph.c        |   63 ++++++++++++++++++++++++++++++++++++++++++-------------
 t/t4202-log.sh |    6 +---
 2 files changed, 50 insertions(+), 19 deletions(-)

diff --git a/graph.c b/graph.c
index 06fbeb6..f3fa253 100644
--- a/graph.c
+++ b/graph.c
@@ -47,20 +47,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
  * - Limit the number of columns, similar to the way gitk does.
  *   If we reach more than a specified number of columns, omit
  *   sections of some columns.
- *
- * - The output during the GRAPH_PRE_COMMIT and GRAPH_COLLAPSING states
- *   could be made more compact by printing horizontal lines, instead of
- *   long diagonal lines.  For example, during collapsing, something like
- *   this:          instead of this:
- *   | | | | |      | | | | |
- *   | |_|_|/       | | | |/
- *   |/| | |        | | |/|
- *   | | | |        | |/| |
- *                  |/| | |
- *                  | | | |
- *
- *   If there are several parallel diagonal lines, they will need to be
- *   replaced with horizontal lines on subsequent rows.
  */
 
 struct column {
@@ -982,6 +968,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 {
 	int i;
 	int *tmp_mapping;
+	short used_horizontal = 0;
+	int horizontal_edge = -1;
+	int horizontal_edge_target = -1;
 
 	/*
 	 * Clear out the new_mapping array
@@ -1019,6 +1008,23 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			 * Move to the left by one
 			 */
 			graph->new_mapping[i - 1] = target;
+			/*
+			 * If there isn't already an edge moving horizontally
+			 * select this one.
+			 */
+			if (horizontal_edge == -1) {
+				int j;
+				horizontal_edge = i;
+				horizontal_edge_target = target;
+				/*
+				 * The variable target is the index of the graph
+				 * column, and therefore target*2+3 is the
+				 * actual screen column of the first horizontal
+				 * line.
+				 */
+				for (j = (target * 2)+3; j < (i - 2); j += 2)
+					graph->new_mapping[j] = target;
+			}
 		} else if (graph->new_mapping[i - 1] == target) {
 			/*
 			 * There is a branch line to our left
@@ -1039,10 +1045,21 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			 *
 			 * The space just to the left of this
 			 * branch should always be empty.
+			 *
+			 * The branch to the left of that space
+			 * should be our eventual target.
 			 */
 			assert(graph->new_mapping[i - 1] > target);
 			assert(graph->new_mapping[i - 2] < 0);
+			assert(graph->new_mapping[i - 3] == target);
 			graph->new_mapping[i - 2] = target;
+			/*
+			 * Mark this branch as the horizontal edge to
+			 * prevent any other edges from moving
+			 * horizontally.
+			 */
+			if (horizontal_edge == -1)
+				horizontal_edge = i;
 		}
 	}
 
@@ -1061,8 +1078,24 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
 			strbuf_write_column(sb, &graph->new_columns[target], '|');
-		else
+		else if (target == horizontal_edge_target &&
+			 i != horizontal_edge - 1) {
+				/*
+				 * Set the mappings for all but the
+				 * first segment to -1 so that they
+				 * won't continue into the next line.
+				 */
+				if (i != (target * 2)+3)
+					graph->new_mapping[i] = -1;
+				used_horizontal = 1;
+			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_pad_horizontally(graph, sb, graph->mapping_size);
diff --git a/t/t4202-log.sh b/t/t4202-log.sh
index 67f983f..076f79e 100755
--- a/t/t4202-log.sh
+++ b/t/t4202-log.sh
@@ -324,14 +324,12 @@ cat > expect <<\EOF
 * | | |   Merge branch 'side'
 |\ \ \ \
 | * | | | side-2
-| | | |/
-| | |/|
+| | |_|/
 | |/| |
 | * | | side-1
 * | | | Second
 * | | | sixth
-| | |/
-| |/|
+| |_|/
 |/| |
 * | | fifth
 * | | fourth
-- 
1.5.6.3

Re: [PATCH v2 (resend)] graph API: Use horizontal lines for more compact graphs

[Junio C Hamano]

Allan Caffee <allan.caffee@gmail.com> writes:

> Junio, is this patch acceptable for inclusion?

I think your patch is an improvement, and it is queued as part of the
first batch post 1.6.3.

As a general guideline:

 - after -rc0, we do not take any feature enhancement patches that has not
   been discussed on the list before -rc0 was tagged;

 - after -rc1, we only take documentation updates, trivial fixes, and
   fixes (not necessarily trivial) to issues introduced since the last
   release (i.e. regression fix);

 - after -rc2, we only take documentation updates and regression fixes;


By the way, your Mail-Followup-To seems to be misconfigured.