[PATCH] graph API: Added logic for colored edges

[PATCH] graph API: Added logic for colored edges

[Allan Caffee]

Modified the graph drawing logic to colorize edges based on parent-child
relationships similiarly to gitk.

Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
---
It seemed like it was time for another iteration so here it is.
Changes this round include: (Only the first two were actually posted
to the list as full patches.)

* graph.c: avoid compile warnings (Thanks Johannes)

* --graph: respect --no-color (Thanks Johannes)

* Remove some outdated TODO comments

* Avoid using forward declarations

* Remove commented out debugging code

* Avoid an unnecessary function call

* Refactor/rename some local functions
I replaced get_next_column_column color with graph_increment_column_color since
the return value is never actually used.  I also renamed
get_current_column_color to graph_get_current_column_color.

* Handle column colors as const pointers
The color codes used should never be modified once we begin graphing,
so columns should store/handle them as const char*.

* graph API: Add handling for merges with 3+ parents
I accidentally left this one out of the first round.

~Allan

 color.h |    1 +
 graph.c |  175 +++++++++++++++++++++++++++++++++++++++++++++++++++-----------
 2 files changed, 145 insertions(+), 31 deletions(-)

diff --git a/color.h b/color.h
index 6846be1..18abeb7 100644
--- a/color.h
+++ b/color.h
@@ -11,6 +11,7 @@
 #define GIT_COLOR_GREEN		"\033[32m"
 #define GIT_COLOR_YELLOW	"\033[33m"
 #define GIT_COLOR_BLUE		"\033[34m"
+#define GIT_COLOR_MAGENTA	"\033[35m"
 #define GIT_COLOR_CYAN		"\033[36m"
 #define GIT_COLOR_BG_RED	"\033[41m"
 
diff --git a/graph.c b/graph.c
index 162a516..0e112d7 100644
--- a/graph.c
+++ b/graph.c
@@ -1,5 +1,6 @@
 #include "cache.h"
 #include "commit.h"
+#include "color.h"
 #include "graph.h"
 #include "diff.h"
 #include "revision.h"
@@ -43,10 +44,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
 
 /*
  * TODO:
- * - Add colors to the graph.
- *   Pick a color for each column, and print all characters
- *   in that column with the specified color.
- *
  * - 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.
@@ -72,11 +69,21 @@ struct column {
 	 */
 	struct commit *commit;
 	/*
-	 * XXX: Once we add support for colors, struct column could also
-	 * contain the color of its branch line.
+	 * The color to (optionally) print this column in.
 	 */
+	const char *color;
 };
 
+static void strbuf_write_column(struct strbuf *sb, const struct column *c,
+		const char *s)
+{
+	if (c->color)
+		strbuf_addstr(sb, c->color);
+	strbuf_addstr(sb, s);
+	if (c->color)
+		strbuf_addstr(sb, GIT_COLOR_RESET);
+}
+
 enum graph_state {
 	GRAPH_PADDING,
 	GRAPH_SKIP,
@@ -86,6 +93,24 @@ enum graph_state {
 	GRAPH_COLLAPSING
 };
 
+/*
+ * The list of available column colors.
+ */
+static char column_colors[][COLOR_MAXLEN] = {
+	GIT_COLOR_RED,
+	GIT_COLOR_GREEN,
+	GIT_COLOR_YELLOW,
+	GIT_COLOR_BLUE,
+	GIT_COLOR_MAGENTA,
+	GIT_COLOR_CYAN,
+	GIT_COLOR_BOLD GIT_COLOR_RED,
+	GIT_COLOR_BOLD GIT_COLOR_GREEN,
+	GIT_COLOR_BOLD GIT_COLOR_YELLOW,
+	GIT_COLOR_BOLD GIT_COLOR_BLUE,
+	GIT_COLOR_BOLD GIT_COLOR_MAGENTA,
+	GIT_COLOR_BOLD GIT_COLOR_CYAN,
+};
+
 struct git_graph {
 	/*
 	 * The commit currently being processed
@@ -185,6 +210,11 @@ struct git_graph {
 	 * temporary array each time we have to output a collapsing line.
 	 */
 	int *new_mapping;
+	/*
+	 * The current default column color being used.  This is
+	 * stored as an index into the array column_colors.
+	 */
+	short default_column_color;
 };
 
 struct git_graph *graph_init(struct rev_info *opt)
@@ -201,6 +231,7 @@ struct git_graph *graph_init(struct rev_info *opt)
 	graph->num_columns = 0;
 	graph->num_new_columns = 0;
 	graph->mapping_size = 0;
+	graph->default_column_color = 0;
 
 	/*
 	 * Allocate a reasonably large default number of columns
@@ -312,6 +343,33 @@ static struct commit_list *first_interesting_parent(struct git_graph *graph)
 	return next_interesting_parent(graph, parents);
 }
 
+static const char* graph_get_current_column_color(const struct git_graph* graph)
+{
+	if (!DIFF_OPT_TST(&graph->revs->diffopt, COLOR_DIFF))
+		return NULL;
+	return column_colors[graph->default_column_color];
+}
+
+/*
+ * Update the graph's default column color.
+ */
+static void graph_increment_column_color(struct git_graph* graph)
+{
+	graph->default_column_color = (graph->default_column_color + 1) %
+		ARRAY_SIZE(column_colors);
+}
+
+static const char * graph_find_commit_color(const struct git_graph *graph,
+				      const struct commit *commit)
+{
+	int i;
+	for (i = 0; i < graph->num_columns; i++) {
+		if (graph->columns[i].commit == commit)
+			return graph->columns[i].color;
+	}
+	return graph_get_current_column_color(graph);
+}
+
 static void graph_insert_into_new_columns(struct git_graph *graph,
 					  struct commit *commit,
 					  int *mapping_index)
@@ -334,6 +392,7 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 	 * This commit isn't already in new_columns.  Add it.
 	 */
 	graph->new_columns[graph->num_new_columns].commit = commit;
+	graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit);
 	graph->mapping[*mapping_index] = graph->num_new_columns;
 	*mapping_index += 2;
 	graph->num_new_columns++;
@@ -445,6 +504,12 @@ static void graph_update_columns(struct git_graph *graph)
 			for (parent = first_interesting_parent(graph);
 			     parent;
 			     parent = next_interesting_parent(graph, parent)) {
+				/*
+				 * If this is a merge increment the current
+				 * color.
+				 */
+				if (graph->num_parents > 1)
+					graph_increment_column_color(graph);
 				graph_insert_into_new_columns(graph,
 							      parent->item,
 							      &mapping_idx);
@@ -596,7 +661,7 @@ 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_addstr(sb, "| ");
+		strbuf_write_column(sb, &graph->new_columns[i], "| ");
 	}
 
 	graph_pad_horizontally(graph, sb);
@@ -648,8 +713,11 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 	for (i = 0; i < graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		if (col->commit == graph->commit) {
+			struct strbuf tmp = STRBUF_INIT;
 			seen_this = 1;
-			strbuf_addf(sb, "| %*s", graph->expansion_row, "");
+			strbuf_addf(&tmp, "| %*s", graph->expansion_row, "");
+			strbuf_write_column(sb, col, tmp.buf);
+			strbuf_release(&tmp);
 		} else if (seen_this && (graph->expansion_row == 0)) {
 			/*
 			 * This is the first line of the pre-commit output.
@@ -662,13 +730,13 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				strbuf_addstr(sb, "\\ ");
+				strbuf_write_column(sb, col, "\\ ");
 			else
-				strbuf_addstr(sb, "| ");
+				strbuf_write_column(sb, col, "| ");
 		} else if (seen_this && (graph->expansion_row > 0)) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, "\\ ");
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, "| ");
 		}
 	}
 
@@ -728,6 +796,7 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 	 */
 	seen_this = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
+		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
 		if (i == graph->num_columns) {
 			if (seen_this)
@@ -744,14 +813,25 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 			if (graph->num_parents < 3)
 				strbuf_addch(sb, ' ');
 			else {
+				/*
+				 * Here dashless_commits represents the
+				 * number of parents which don't need
+				 * to have dashes (because their edges
+				 * fit neatly under the commit).
+				 */
+				const int dashless_commits = 2;
 				int num_dashes =
-					((graph->num_parents - 2) * 2) - 1;
+					((graph->num_parents - dashless_commits) * 2) - 1;
 				for (j = 0; j < num_dashes; j++)
-					strbuf_addch(sb, '-');
-				strbuf_addstr(sb, ". ");
+					strbuf_write_column(sb,
+							    &graph->new_columns[(j / 2) + dashless_commits],
+							    "-");
+				strbuf_write_column(sb,
+						    &graph->new_columns[(j / 2) + dashless_commits],
+						    ". ");
 			}
 		} else if (seen_this && (graph->num_parents > 2)) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, "\\ ");
 		} else if (seen_this && (graph->num_parents == 2)) {
 			/*
 			 * This is a 2-way merge commit.
@@ -768,11 +848,11 @@ 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_addstr(sb, "\\ ");
+				strbuf_write_column(sb, col, "\\ ");
 			else
-				strbuf_addstr(sb, "| ");
+				strbuf_write_column(sb, col, "| ");
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, "| ");
 		}
 	}
 
@@ -789,6 +869,17 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
+inline struct column* find_new_column_by_commit(struct git_graph *graph,
+						struct commit *commit)
+{
+	int i;
+	for (i = 0; i < graph->num_new_columns; i++) {
+		if (graph->new_columns[i].commit == commit)
+			return &graph->new_columns[i];
+	}
+	return 0;
+}
+
 static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
@@ -798,24 +889,43 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 	 * Output the post-merge row
 	 */
 	for (i = 0; i <= graph->num_columns; i++) {
+		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
 		if (i == graph->num_columns) {
 			if (seen_this)
 				break;
 			col_commit = graph->commit;
 		} else {
-			col_commit = graph->columns[i].commit;
+			col_commit = col->commit;
 		}
 
 		if (col_commit == graph->commit) {
+			/*
+			 * Since the current commit is a merge find
+			 * the columns for the parent commits in
+			 * new_columns and use those to format the
+			 * edges.
+			 */
+			struct commit_list *parents = NULL;
+			struct column *par_column;
 			seen_this = 1;
-			strbuf_addch(sb, '|');
-			for (j = 0; j < graph->num_parents - 1; j++)
-				strbuf_addstr(sb, "\\ ");
+			parents = first_interesting_parent(graph);
+			assert(parents);
+			par_column = find_new_column_by_commit(graph,parents->item);
+			assert(par_column);
+
+			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, "\\ ");
+			}
 		} else if (seen_this) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, "\\ ");
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, "| ");
 		}
 	}
 
@@ -912,9 +1022,11 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 		if (target < 0)
 			strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
-			strbuf_addch(sb, '|');
-		else
-			strbuf_addch(sb, '/');
+			strbuf_write_column(sb, &graph->new_columns[target], "|");
+		else {
+			strbuf_write_column(sb, &graph->new_columns[target], "/");
+
+		}
 	}
 
 	graph_pad_horizontally(graph, sb);
@@ -979,9 +1091,10 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 	 * children that we have already processed.)
 	 */
 	for (i = 0; i < graph->num_columns; i++) {
-		struct commit *col_commit = graph->columns[i].commit;
+		struct column *col = &graph->columns[i];
+		struct commit *col_commit = col->commit;
 		if (col_commit == graph->commit) {
-			strbuf_addch(sb, '|');
+			strbuf_write_column(sb, col, "|");
 
 			if (graph->num_parents < 3)
 				strbuf_addch(sb, ' ');
@@ -991,7 +1104,7 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 					strbuf_addch(sb, ' ');
 			}
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, "| ");
 		}
 	}
 
-- 
1.5.6.3

Re: [PATCH] graph API: Added logic for colored edges

[Junio C Hamano]

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

> @@ -72,11 +69,21 @@ struct column {
>  	 */
>  	struct commit *commit;
>  	/*
> -	 * XXX: Once we add support for colors, struct column could also
> -	 * contain the color of its branch line.
> +	 * The color to (optionally) print this column in.
>  	 */
> +	const char *color;

You already use short for git_graph.default_column_color and I suspect in
the longer term you want to make this one an index into column_colors[]
array the same way.  We may someday decide to support non-ANSI color
scheme using ncurses or something, and at that point the "hardware color"
constants like GIT_COLOR_RED and friends may change from strings to small
integers we use to call our (yet to be written) curses interface layer
with.

> @@ -312,6 +343,33 @@ static struct commit_list *first_interesting_parent(struct git_graph *graph)
>  	return next_interesting_parent(graph, parents);
>  }
>  
> +static const char* graph_get_current_column_color(const struct git_graph* graph)

Style.  Asterisk comes next to identifiers, not types (the parameter to
graph_increment_column_color has the same issue).

	static const char *graph_...color(const struct git_graph *graph)

> @@ -596,7 +661,7 @@ 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_addstr(sb, "| ");
> +		strbuf_write_column(sb, &graph->new_columns[i], "| ");

Hmmm, this forbids us to use reverse color in the color palette because
that would highlight the trailing whitespace.  Is that something we care
about, or a reversed "|", "/" and "\" are already too ugly that we won't
want to support them?

> @@ -648,8 +713,11 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>  	for (i = 0; i < graph->num_columns; i++) {
>  		struct column *col = &graph->columns[i];
>  		if (col->commit == graph->commit) {
> +			struct strbuf tmp = STRBUF_INIT;
>  			seen_this = 1;
> -			strbuf_addf(sb, "| %*s", graph->expansion_row, "");
> +			strbuf_addf(&tmp, "| %*s", graph->expansion_row, "");
> +			strbuf_write_column(sb, col, tmp.buf);
> +			strbuf_release(&tmp);

Same here.

> @@ -662,13 +730,13 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
>  			 */
>  			if (graph->prev_state == GRAPH_POST_MERGE &&
>  			    graph->prev_commit_index < i)
> -				strbuf_addstr(sb, "\\ ");
> +				strbuf_write_column(sb, col, "\\ ");
>  			else
> -				strbuf_addstr(sb, "| ");
> +				strbuf_write_column(sb, col, "| ");
>  		} else if (seen_this && (graph->expansion_row > 0)) {
> -			strbuf_addstr(sb, "\\ ");
> +			strbuf_write_column(sb, col, "\\ ");
>  		} else {
> -			strbuf_addstr(sb, "| ");
> +			strbuf_write_column(sb, col, "| ");
>  		}
>  	}

Likewise.

> @@ -744,14 +813,25 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  			if (graph->num_parents < 3)
>  				strbuf_addch(sb, ' ');
>  			else {
> +				/*
> +				 * Here dashless_commits represents the
> +				 * number of parents which don't need
> +				 * to have dashes (because their edges
> +				 * fit neatly under the commit).
> +				 */
> +				const int dashless_commits = 2;
>  				int num_dashes =
> -					((graph->num_parents - 2) * 2) - 1;
> +					((graph->num_parents - dashless_commits) * 2) - 1;
>  				for (j = 0; j < num_dashes; j++)
> -					strbuf_addch(sb, '-');
> -				strbuf_addstr(sb, ". ");
> +					strbuf_write_column(sb,
> +							    &graph->new_columns[(j / 2) + dashless_commits],
> +							    "-");
> +				strbuf_write_column(sb,
> +						    &graph->new_columns[(j / 2) + dashless_commits],
> +						    ". ");

The nesting seems to be becoming too deep and the body of the for loop is
getting too long.  Time to make it a helper function that handles only one
column, perhaps?

Re: [PATCH] graph API: Added logic for colored edges

[Allan Caffee]

On Wed, 08 Apr 2009, Junio C Hamano wrote:
> Allan Caffee <allan.caffee@gmail.com> writes:
> 
> > @@ -72,11 +69,21 @@ struct column {
> >  	 */
> >  	struct commit *commit;
> >  	/*
> > -	 * XXX: Once we add support for colors, struct column could also
> > -	 * contain the color of its branch line.
> > +	 * The color to (optionally) print this column in.
> >  	 */
> > +	const char *color;
> 
> You already use short for git_graph.default_column_color and I suspect in
> the longer term you want to make this one an index into column_colors[]
> array the same way.  We may someday decide to support non-ANSI color
> scheme using ncurses or something, and at that point the "hardware color"
> constants like GIT_COLOR_RED and friends may change from strings to small
> integers we use to call our (yet to be written) curses interface layer
> with.

The problem with making it an index into the column_colors array is that
we don't have a convenient place to test whether the user actually wants
color.  We can't do it in strbuf_write_column because AFAIK there's no
way to get the rev-info to test the options.  I suppose we could define
GIT_NOT_A_COLOR to -1 and just set the color to that when we don't
intend to use color.  (Either way I should probably change that to an
unsigned short.)  What do you think?

> > @@ -312,6 +343,33 @@ static struct commit_list *first_interesting_parent(struct git_graph *graph)
> >  	return next_interesting_parent(graph, parents);
> >  }
> >  
> > +static const char* graph_get_current_column_color(const struct git_graph* graph)
> 
> Style.  Asterisk comes next to identifiers, not types (the parameter to
> graph_increment_column_color has the same issue).

Okay.

> 	static const char *graph_...color(const struct git_graph *graph)
> 
> > @@ -596,7 +661,7 @@ 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_addstr(sb, "| ");
> > +		strbuf_write_column(sb, &graph->new_columns[i], "| ");
> 
> Hmmm, this forbids us to use reverse color in the color palette because
> that would highlight the trailing whitespace.  Is that something we care
> about, or a reversed "|", "/" and "\" are already too ugly that we won't
> want to support them?

Personally I don't think it's a good idea to limit the colors just
because they would "look funny".  It seems to me that if the user wanted
the background colored they would expect to see just the line segment
colored and not the whitespace.

The simplest way to fix this AFAIKS is to change strbuf_write_column to
take a single character and change the existing code to add spaces in
seperately.

/* For example */
strbuf_write_column(sb, &graph->new_columns[i], "| ");
/* Becomes */
strbuf_write_column(sb, &graph->new_columns[i], '|');
strbuf_addch(sb, ' ');

This would fix the problem at the minor expense of adding ~15 lines of
code.

> [...]
> 
> > @@ -744,14 +813,25 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
> >  			if (graph->num_parents < 3)
> >  				strbuf_addch(sb, ' ');
> >  			else {
> > +				/*
> > +				 * Here dashless_commits represents the
> > +				 * number of parents which don't need
> > +				 * to have dashes (because their edges
> > +				 * fit neatly under the commit).
> > +				 */
> > +				const int dashless_commits = 2;
> >  				int num_dashes =
> > -					((graph->num_parents - 2) * 2) - 1;
> > +					((graph->num_parents - dashless_commits) * 2) - 1;
> >  				for (j = 0; j < num_dashes; j++)
> > -					strbuf_addch(sb, '-');
> > -				strbuf_addstr(sb, ". ");
> > +					strbuf_write_column(sb,
> > +							    &graph->new_columns[(j / 2) + dashless_commits],
> > +							    "-");
> > +				strbuf_write_column(sb,
> > +						    &graph->new_columns[(j / 2) + dashless_commits],
> > +						    ". ");
> 
> The nesting seems to be becoming too deep and the body of the for loop is
> getting too long.  Time to make it a helper function that handles only one
> column, perhaps?

If I understand this correctly in order to write a per column function
would be like:

/*
 * Draw one peice of the commit line and return the new value of
 * seen_this.
 */
static int graph_commit_line_draw_column(struct git_graph *graph, 
                                         struct strbuf *sb,
                                         int i, int seen_this)

Which moves the entire body of the for loop into a function and only
reduces the indentation by one level.  Am I missing something?

Re: [PATCH] graph API: Added logic for colored edges

[Junio C Hamano]

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

> The problem with making it an index into the column_colors array is that
> we don't have a convenient place to test whether the user actually wants
> color.  We can't do it in strbuf_write_column because AFAIK there's no
> way to get the rev-info to test the options.  I suppose we could define
> GIT_NOT_A_COLOR to -1 and just set the color to that when we don't
> intend to use color.  (Either way I should probably change that to an
> unsigned short.)  What do you think?

Sounds sensible.

Re: [PATCH] graph API: Added logic for colored edges

[Teemu Likonen]

On 2009-04-07 14:57 (-0400), Allan Caffee wrote:

> Modified the graph drawing logic to colorize edges based on
> parent-child relationships similiarly to gitk.

I like the colored graph very much, thanks. Unfortunately there are some
problems with aligning of log messages and headers. For example, try
this in git.git repository:


$ git log -1 --graph 796b137

*   commit 796b13781aecce551b8f92049a66646e60f31dce
|\ Merge: 6da14ee db12d97
| | Author: Junio C Hamano <gitster@pobox.com>
| | Date:   2009-04-08 23:41:27 -0700


Without colors or without your patch the alignment is correct:

$ git log -1 --graph --no-color 796b137

*   commit 796b13781aecce551b8f92049a66646e60f31dce
|\  Merge: 6da14ee db12d97
| | Author: Junio C Hamano <gitster@pobox.com>
| | Date:   2009-04-08 23:41:27 -0700


(Perhaps the "Merge:" header could have two spaces befor the data, but
this is  unrelated to --graph.)

Re: [PATCH] graph API: Added logic for colored edges

[Allan Caffee]

On Thu, 09 Apr 2009, Teemu Likonen wrote:
> On 2009-04-07 14:57 (-0400), Allan Caffee wrote:
> 
> > Modified the graph drawing logic to colorize edges based on
> > parent-child relationships similiarly to gitk.
> 
> I like the colored graph very much, thanks. Unfortunately there are some
> problems with aligning of log messages and headers. For example, try
> this in git.git repository:
> 
> 
> $ git log -1 --graph 796b137
> 
> *   commit 796b13781aecce551b8f92049a66646e60f31dce
> |\ Merge: 6da14ee db12d97
> | | Author: Junio C Hamano <gitster@pobox.com>
> | | Date:   2009-04-08 23:41:27 -0700
> 
> 
> Without colors or without your patch the alignment is correct:
> 
> $ git log -1 --graph --no-color 796b137
> 
> *   commit 796b13781aecce551b8f92049a66646e60f31dce
> |\  Merge: 6da14ee db12d97
> | | Author: Junio C Hamano <gitster@pobox.com>
> | | Date:   2009-04-08 23:41:27 -0700
> 
> 
> (Perhaps the "Merge:" header could have two spaces befor the data, but
> this is  unrelated to --graph.)

Thanks for the feedback!  The problem here is that
graph_horizontal_padding was counting the number of characters in the
strbuf in order to decide how much whitespace to pad the row with.  The
ANSI escape sequences for colors and attributes are not printable
characters but do contribute to the length of the strbuf.  This can be
fixed by adding a new function that counts only printing
characters/spaces.  I'll include this in my next round.  

[PATCH v3] graph API: Added logic for colored edges

[Allan Caffee]

Modified the graph drawing logic to colorize edges based on parent-child
relationships similiarly to gitk.

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

Here's a list of the changes this round (I can send individual patches
if it's easier to review):

* graph API: Fix graph_pad_horizontal to work properly with colors
    The horizontal padding was counting the number of characters in the
strbuf in order to decide how much whitespace to pad the row with.
The ANSI escape sequences for colors and attributes are not printable
characters but do contribute to the length of the strbuf.  This fix
teaches strbuf's to count printing characters (i.e. characters that
consume space).
* graph.c: Add graph_draw_octopus_merge() to simplify graph_output_commit_line()
* --graph: Fix whitespace discoloration
    Background colors now work as expected (but boy are they ugly ;).
* graph.c: Store colors as unsigned short
* graph: Fixed up some stylistic issues with pointers

~Allan

 color.h  |    1 +
 graph.c  |  212 +++++++++++++++++++++++++++++++++++++++++++++++++------------
 strbuf.c |   39 +++++++++++
 strbuf.h |    1 +
 4 files changed, 211 insertions(+), 42 deletions(-)

diff --git a/color.h b/color.h
index 6846be1..18abeb7 100644
--- a/color.h
+++ b/color.h
@@ -11,6 +11,7 @@
 #define GIT_COLOR_GREEN		"\033[32m"
 #define GIT_COLOR_YELLOW	"\033[33m"
 #define GIT_COLOR_BLUE		"\033[34m"
+#define GIT_COLOR_MAGENTA	"\033[35m"
 #define GIT_COLOR_CYAN		"\033[36m"
 #define GIT_COLOR_BG_RED	"\033[41m"
 
diff --git a/graph.c b/graph.c
index 162a516..beb622a 100644
--- a/graph.c
+++ b/graph.c
@@ -1,5 +1,6 @@
 #include "cache.h"
 #include "commit.h"
+#include "color.h"
 #include "graph.h"
 #include "diff.h"
 #include "revision.h"
@@ -43,10 +44,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
 
 /*
  * TODO:
- * - Add colors to the graph.
- *   Pick a color for each column, and print all characters
- *   in that column with the specified color.
- *
  * - 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.
@@ -72,11 +69,14 @@ struct column {
 	 */
 	struct commit *commit;
 	/*
-	 * XXX: Once we add support for colors, struct column could also
-	 * contain the color of its branch line.
+	 * The color to (optionally) print this column in.  This is an
+	 * index into column_colors.
 	 */
+	unsigned short color;
 };
 
+const unsigned short GIT_NOT_A_COLOR = -1;
+
 enum graph_state {
 	GRAPH_PADDING,
 	GRAPH_SKIP,
@@ -86,6 +86,39 @@ enum graph_state {
 	GRAPH_COLLAPSING
 };
 
+/*
+ * The list of available column colors.
+ */
+static char column_colors[][COLOR_MAXLEN] = {
+	GIT_COLOR_RED,
+	GIT_COLOR_GREEN,
+	GIT_COLOR_YELLOW,
+	GIT_COLOR_BLUE,
+	GIT_COLOR_MAGENTA,
+	GIT_COLOR_CYAN,
+	GIT_COLOR_BOLD GIT_COLOR_RED,
+	GIT_COLOR_BOLD GIT_COLOR_GREEN,
+	GIT_COLOR_BOLD GIT_COLOR_YELLOW,
+	GIT_COLOR_BOLD GIT_COLOR_BLUE,
+	GIT_COLOR_BOLD GIT_COLOR_MAGENTA,
+	GIT_COLOR_BOLD GIT_COLOR_CYAN,
+};
+
+static const char *column_get_color_code(const struct column *c)
+{
+	return column_colors[c->color];
+}
+
+static void strbuf_write_column(struct strbuf *sb, const struct column *c,
+				char col_char)
+{
+	if (c->color != GIT_NOT_A_COLOR)
+		strbuf_addstr(sb, column_get_color_code(c));
+	strbuf_addch(sb, col_char);
+	if (c->color != GIT_NOT_A_COLOR)
+		strbuf_addstr(sb, GIT_COLOR_RESET);
+}
+
 struct git_graph {
 	/*
 	 * The commit currently being processed
@@ -185,6 +218,11 @@ struct git_graph {
 	 * temporary array each time we have to output a collapsing line.
 	 */
 	int *new_mapping;
+	/*
+	 * The current default column color being used.  This is
+	 * stored as an index into the array column_colors.
+	 */
+	unsigned short default_column_color;
 };
 
 struct git_graph *graph_init(struct rev_info *opt)
@@ -201,6 +239,7 @@ struct git_graph *graph_init(struct rev_info *opt)
 	graph->num_columns = 0;
 	graph->num_new_columns = 0;
 	graph->mapping_size = 0;
+	graph->default_column_color = 0;
 
 	/*
 	 * Allocate a reasonably large default number of columns
@@ -312,6 +351,33 @@ static struct commit_list *first_interesting_parent(struct git_graph *graph)
 	return next_interesting_parent(graph, parents);
 }
 
+inline unsigned short graph_get_current_column_color(const struct git_graph *graph)
+{
+	if (!DIFF_OPT_TST(&graph->revs->diffopt, COLOR_DIFF))
+		return GIT_NOT_A_COLOR;
+	return graph->default_column_color;
+}
+
+/*
+ * Update the graph's default column color.
+ */
+static void graph_increment_column_color(struct git_graph *graph)
+{
+	graph->default_column_color = (graph->default_column_color + 1) %
+		ARRAY_SIZE(column_colors);
+}
+
+inline unsigned short graph_find_commit_color(const struct git_graph *graph,
+					      const struct commit *commit)
+{
+	int i;
+	for (i = 0; i < graph->num_columns; i++) {
+		if (graph->columns[i].commit == commit)
+			return graph->columns[i].color;
+	}
+	return graph_get_current_column_color(graph);
+}
+
 static void graph_insert_into_new_columns(struct git_graph *graph,
 					  struct commit *commit,
 					  int *mapping_index)
@@ -334,6 +400,7 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 	 * This commit isn't already in new_columns.  Add it.
 	 */
 	graph->new_columns[graph->num_new_columns].commit = commit;
+	graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit);
 	graph->mapping[*mapping_index] = graph->num_new_columns;
 	*mapping_index += 2;
 	graph->num_new_columns++;
@@ -445,6 +512,12 @@ static void graph_update_columns(struct git_graph *graph)
 			for (parent = first_interesting_parent(graph);
 			     parent;
 			     parent = next_interesting_parent(graph, parent)) {
+				/*
+				 * If this is a merge increment the current
+				 * color.
+				 */
+				if (graph->num_parents > 1)
+					graph_increment_column_color(graph);
 				graph_insert_into_new_columns(graph,
 							      parent->item,
 							      &mapping_idx);
@@ -569,11 +642,11 @@ 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.
 	 */
-	int extra;
-	if (sb->len >= graph->width)
+	int extra, printing;
+	printing = strbuf_count_printing_chars(sb);
+	if (printing >= graph->width)
 		return;
-
-	extra = graph->width - sb->len;
+	extra = graph->width - printing;
 	strbuf_addf(sb, "%*s", (int) extra, "");
 }
 
@@ -596,7 +669,8 @@ 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_addstr(sb, "| ");
+		strbuf_write_column(sb, &graph->new_columns[i], '|');
+		strbuf_addch(sb, ' ');
 	}
 
 	graph_pad_horizontally(graph, sb);
@@ -649,7 +723,8 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		struct column *col = &graph->columns[i];
 		if (col->commit == graph->commit) {
 			seen_this = 1;
-			strbuf_addf(sb, "| %*s", graph->expansion_row, "");
+			strbuf_write_column(sb, col, '|');
+			strbuf_addf(sb, " %*s", graph->expansion_row, "");
 		} else if (seen_this && (graph->expansion_row == 0)) {
 			/*
 			 * This is the first line of the pre-commit output.
@@ -662,14 +737,15 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				strbuf_addstr(sb, "\\ ");
+				strbuf_write_column(sb, col, '\\');
 			else
-				strbuf_addstr(sb, "| ");
+				strbuf_write_column(sb, col, '|');
 		} else if (seen_this && (graph->expansion_row > 0)) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, '\\');
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
 		}
+		strbuf_addch(sb, ' ');
 	}
 
 	graph_pad_horizontally(graph, sb);
@@ -714,10 +790,30 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 	strbuf_addch(sb, '*');
 }
 
+inline void graph_draw_octopus_merge(const struct git_graph *graph,
+				     struct strbuf *sb)
+{
+	/*
+	 * Here dashless_commits represents the number of parents
+	 * which don't need to have dashes (because their edges fit
+	 * neatly under the commit).
+	 */
+	const int dashless_commits = 2;
+	int col_num, i;
+	int num_dashes =
+		((graph->num_parents - dashless_commits) * 2) - 1;
+	for (i = 0; i < num_dashes; i++) {
+		col_num = (i / 2) + dashless_commits;
+		strbuf_write_column(sb, &graph->new_columns[col_num], '-');
+	}
+	col_num = (i / 2) + dashless_commits;
+	strbuf_write_column(sb, &graph->new_columns[col_num], '.');
+}
+
 static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
-	int i, j;
+	int i;
 
 	/*
 	 * Output the row containing this commit
@@ -728,6 +824,7 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 	 */
 	seen_this = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
+		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
 		if (i == graph->num_columns) {
 			if (seen_this)
@@ -741,17 +838,10 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 			seen_this = 1;
 			graph_output_commit_char(graph, sb);
 
-			if (graph->num_parents < 3)
-				strbuf_addch(sb, ' ');
-			else {
-				int num_dashes =
-					((graph->num_parents - 2) * 2) - 1;
-				for (j = 0; j < num_dashes; j++)
-					strbuf_addch(sb, '-');
-				strbuf_addstr(sb, ". ");
-			}
+			if (graph->num_parents > 3)
+				graph_draw_octopus_merge(graph, sb);
 		} else if (seen_this && (graph->num_parents > 2)) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, '\\');
 		} else if (seen_this && (graph->num_parents == 2)) {
 			/*
 			 * This is a 2-way merge commit.
@@ -768,12 +858,13 @@ 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_addstr(sb, "\\ ");
+				strbuf_write_column(sb, col, '\\');
 			else
-				strbuf_addstr(sb, "| ");
+				strbuf_write_column(sb, col, '|');
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
 		}
+		strbuf_addch(sb, ' ');
 	}
 
 	graph_pad_horizontally(graph, sb);
@@ -789,6 +880,17 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
+inline struct column *find_new_column_by_commit(struct git_graph *graph,
+						struct commit *commit)
+{
+	int i;
+	for (i = 0; i < graph->num_new_columns; i++) {
+		if (graph->new_columns[i].commit == commit)
+			return &graph->new_columns[i];
+	}
+	return 0;
+}
+
 static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
@@ -798,24 +900,46 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 	 * Output the post-merge row
 	 */
 	for (i = 0; i <= graph->num_columns; i++) {
+		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
 		if (i == graph->num_columns) {
 			if (seen_this)
 				break;
 			col_commit = graph->commit;
 		} else {
-			col_commit = graph->columns[i].commit;
+			col_commit = col->commit;
 		}
 
 		if (col_commit == graph->commit) {
+			/*
+			 * Since the current commit is a merge find
+			 * the columns for the parent commits in
+			 * new_columns and use those to format the
+			 * edges.
+			 */
+			struct commit_list *parents = NULL;
+			struct column *par_column;
 			seen_this = 1;
-			strbuf_addch(sb, '|');
-			for (j = 0; j < graph->num_parents - 1; j++)
-				strbuf_addstr(sb, "\\ ");
+			parents = first_interesting_parent(graph);
+			assert(parents);
+			par_column = find_new_column_by_commit(graph,parents->item);
+			assert(par_column);
+
+			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, ' ');
+			}
 		} else if (seen_this) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, '\\');
+			strbuf_addch(sb, ' ');
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
+			strbuf_addch(sb, ' ');
 		}
 	}
 
@@ -912,9 +1036,11 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 		if (target < 0)
 			strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
-			strbuf_addch(sb, '|');
-		else
-			strbuf_addch(sb, '/');
+			strbuf_write_column(sb, &graph->new_columns[target], '|');
+		else {
+			strbuf_write_column(sb, &graph->new_columns[target], '/');
+
+		}
 	}
 
 	graph_pad_horizontally(graph, sb);
@@ -979,9 +1105,10 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 	 * children that we have already processed.)
 	 */
 	for (i = 0; i < graph->num_columns; i++) {
-		struct commit *col_commit = graph->columns[i].commit;
+		struct column *col = &graph->columns[i];
+		struct commit *col_commit = col->commit;
 		if (col_commit == graph->commit) {
-			strbuf_addch(sb, '|');
+			strbuf_write_column(sb, col, '|');
 
 			if (graph->num_parents < 3)
 				strbuf_addch(sb, ' ');
@@ -991,7 +1118,8 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 					strbuf_addch(sb, ' ');
 			}
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
+			strbuf_addch(sb, ' ');
 		}
 	}
 
diff --git a/strbuf.c b/strbuf.c
index a884960..f525d51 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -1,3 +1,4 @@
+#include <ctype.h>
 #include "cache.h"
 #include "refs.h"
 
@@ -138,6 +139,44 @@ void strbuf_list_free(struct strbuf **sbs)
 	free(sbs);
 }
 
+/*
+ * Return the length of the escape sequence in a string buffer
+ * starting at index i.  If there is no escape sequence starting at
+ * return 0.
+ */
+inline size_t strbuf_esc_sequence_length(const struct strbuf *sb, size_t i)
+{
+	size_t start = i;
+	if (sb->buf[i] != '\033')
+		return 0;
+	++i;
+
+	if (i >= sb->len || sb->buf[i] != '[')
+		return 0;
+	++i;
+	while (i < sb->len && isdigit(sb->buf[i]))
+		++i;
+
+	if (i >= sb->len || sb->buf[i] != 'm')
+		return 0;
+	return i - start;
+}
+
+size_t strbuf_count_printing_chars(const struct strbuf *sb)
+{
+	int i;
+	size_t n = 0;
+	size_t esc_len;
+	for (i = 0; i < sb->len; i++) {
+		esc_len = strbuf_esc_sequence_length(sb, i);
+		if (esc_len)
+			i += esc_len;
+		else if (isgraph(sb->buf[i]) || sb->buf[i] == ' ')
+			++n;
+	}
+	return n;
+}
+
 int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
 {
 	int len = a->len < b->len ? a->len: b->len;
diff --git a/strbuf.h b/strbuf.h
index 9ee908a..3851ddf 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -86,6 +86,7 @@ extern void strbuf_tolower(struct strbuf *);
 extern struct strbuf **strbuf_split(const struct strbuf *, int delim);
 extern void strbuf_list_free(struct strbuf **);
 
+extern size_t strbuf_count_printing_chars(const struct strbuf *sb);
 /*----- add data in your buffer -----*/
 static inline void strbuf_addch(struct strbuf *sb, int c) {
 	strbuf_grow(sb, 1);
-- 
1.5.6.3

Re: [PATCH v3] graph API: Added logic for colored edges

[Junio C Hamano]

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

> diff --git a/graph.c b/graph.c
> index 162a516..beb622a 100644
> --- a/graph.c
> +++ b/graph.c
> @@ -1,5 +1,6 @@
>  #include "cache.h"
>  #include "commit.h"
> +#include "color.h"
>  #include "graph.h"
>  #include "diff.h"
>  #include "revision.h"
> @@ -72,11 +69,14 @@ struct column {
>  	 */
>  	struct commit *commit;
>  	/*
> -	 * XXX: Once we add support for colors, struct column could also
> -	 * contain the color of its branch line.
> +	 * The color to (optionally) print this column in.  This is an
> +	 * index into column_colors.
>  	 */
> +	unsigned short color;
>  };
>  
> +const unsigned short GIT_NOT_A_COLOR = -1;

That (-1) is an unusual value for an *unsigned* short variable.

> @@ -714,10 +790,30 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
>  	strbuf_addch(sb, '*');
>  }
>  
> +inline void graph_draw_octopus_merge(const struct git_graph *graph,
> +				     struct strbuf *sb)
> +{
> +	/*
> +	 * Here dashless_commits represents the number of parents
> +	 * which don't need to have dashes (because their edges fit
> +	 * neatly under the commit).
> +	 */
> +	const int dashless_commits = 2;
> +	int col_num, i;
> +	int num_dashes =
> +		((graph->num_parents - dashless_commits) * 2) - 1;
> +	for (i = 0; i < num_dashes; i++) {
> +		col_num = (i / 2) + dashless_commits;
> +		strbuf_write_column(sb, &graph->new_columns[col_num], '-');

graph.c: In function 'graph_draw_octopus_merge':
graph.c:807: error: 'strbuf_write_column' is static but used in inline function 'graph_draw_octopus_merge' which is not static
graph.c:810: error: 'strbuf_write_column' is static but used in inline function 'graph_draw_octopus_merge' which is not static
make: *** [graph.o] Error 1

In general, I'd prefer people not to say "inline" unless (1) they know
what they are doing, and (2) the code is really performance critical.

At least I do not think the colored commit graph is performance critical,
especially a function that only deals with octopus merges.

Re: [PATCH v3] graph API: Added logic for colored edges

[Allan Caffee]

On Sun, 12 Apr 2009, Junio C Hamano wrote:

> Allan Caffee <allan.caffee@gmail.com> writes:
>
> > diff --git a/graph.c b/graph.c
> > index 162a516..beb622a 100644
> > --- a/graph.c
> > +++ b/graph.c
> > @@ -1,5 +1,6 @@
> >  #include "cache.h"
> >  #include "commit.h"
> > +#include "color.h"
> >  #include "graph.h"
> >  #include "diff.h"
> >  #include "revision.h"
> > @@ -72,11 +69,14 @@ struct column {
> >  	 */
> >  	struct commit *commit;
> >  	/*
> > -	 * XXX: Once we add support for colors, struct column could also
> > -	 * contain the color of its branch line.
> > +	 * The color to (optionally) print this column in.  This is an
> > +	 * index into column_colors.
> >  	 */
> > +	unsigned short color;
> >  };
> >
> > +const unsigned short GIT_NOT_A_COLOR = -1;
>
> That (-1) is an unusual value for an *unsigned* short variable.

Perhaps you would prefer USHRT_MAX?  I noticed that none of the existing
code #includes limits.h.  Is it safe to assume this header is present?

> > @@ -714,10 +790,30 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
> >  	strbuf_addch(sb, '*');
> >  }
> >
> > +inline void graph_draw_octopus_merge(const struct git_graph *graph,
> > +				     struct strbuf *sb)
> > +{
> > +	/*
> > +	 * Here dashless_commits represents the number of parents
> > +	 * which don't need to have dashes (because their edges fit
> > +	 * neatly under the commit).
> > +	 */
> > +	const int dashless_commits = 2;
> > +	int col_num, i;
> > +	int num_dashes =
> > +		((graph->num_parents - dashless_commits) * 2) - 1;
> > +	for (i = 0; i < num_dashes; i++) {
> > +		col_num = (i / 2) + dashless_commits;
> > +		strbuf_write_column(sb, &graph->new_columns[col_num], '-');
>
> graph.c: In function 'graph_draw_octopus_merge':
> graph.c:807: error: 'strbuf_write_column' is static but used in inline function 'graph_draw_octopus_merge' which is not static
> graph.c:810: error: 'strbuf_write_column' is static but used in inline function 'graph_draw_octopus_merge' which is not static
> make: *** [graph.o] Error 1
>
> In general, I'd prefer people not to say "inline" unless (1) they know
> what they are doing, and (2) the code is really performance critical.
>
> At least I do not think the colored commit graph is performance critical,
> especially a function that only deals with octopus merges.

Okay.  I'll remove the inline specifier from all the functions I added.

Re: [PATCH v3] graph API: Added logic for colored edges

[Junio C Hamano]

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

>> > +const unsigned short GIT_NOT_A_COLOR = -1;
>>
>> That (-1) is an unusual value for an *unsigned* short variable.
>
> Perhaps you would prefer USHRT_MAX?  I noticed that none of the existing
> code #includes limits.h.  Is it safe to assume this header is present?

I expected to see something like 

	#define COLUMN_COLORS_MAX (ARRAY_SIZE(column_colors)+1)

	write_with_color(...) {
                if (c->color < COLUMN_COLORS_MAX)
                        add color prefix;
                add string
                if (c->color < COLUMN_COLORS_MAX)
                        add color suffix;
	}

instead, actually, and was a bit surprised with (-1).

[PATCH v4] graph API: Added logic for colored edges

[Allan Caffee]

Modified the graph drawing logic to colorize edges based on parent-child
relationships similiarly to gitk.

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

On Sun, 12 Apr 2009, Junio C Hamano wrote:

> Allan Caffee <allan.caffee@gmail.com> writes:
>
> >> > +const unsigned short GIT_NOT_A_COLOR = -1;
> >>
> >> That (-1) is an unusual value for an *unsigned* short variable.
> >
> > Perhaps you would prefer USHRT_MAX?  I noticed that none of the
> > existing
> > code #includes limits.h.  Is it safe to assume this header is
> > present?
>
> I expected to see something like
>
>       #define COLUMN_COLORS_MAX (ARRAY_SIZE(column_colors)+1)
>
>       write_with_color(...) {
>                 if (c->color < COLUMN_COLORS_MAX)
>                         add color prefix;
>                 add string
>                 if (c->color < COLUMN_COLORS_MAX)
>                         add color suffix;
>       }
>
> instead, actually, and was a bit surprised with (-1).

Junio,

I assumed that the +1 in your example was a typo since AFAIKS ARRAY_SIZE
should give us one past the last index.  If that's not correct let me
know and I'll fix it.

Also if git is to be expanded allow the use of non-ANSI color codes (or
already does so) the strbuf_escape_sequence_length needs to be updated
to accept the relevant escape codes.

Thanks for all the help,
Allan

 color.h  |    1 +
 graph.c  |  212 +++++++++++++++++++++++++++++++++++++++++++++++++------------
 strbuf.c |   39 +++++++++++
 strbuf.h |    1 +
 4 files changed, 211 insertions(+), 42 deletions(-)

diff --git a/color.h b/color.h
index 6846be1..18abeb7 100644
--- a/color.h
+++ b/color.h
@@ -11,6 +11,7 @@
 #define GIT_COLOR_GREEN		"\033[32m"
 #define GIT_COLOR_YELLOW	"\033[33m"
 #define GIT_COLOR_BLUE		"\033[34m"
+#define GIT_COLOR_MAGENTA	"\033[35m"
 #define GIT_COLOR_CYAN		"\033[36m"
 #define GIT_COLOR_BG_RED	"\033[41m"
 
diff --git a/graph.c b/graph.c
index 162a516..1ae7a9c 100644
--- a/graph.c
+++ b/graph.c
@@ -1,5 +1,6 @@
 #include "cache.h"
 #include "commit.h"
+#include "color.h"
 #include "graph.h"
 #include "diff.h"
 #include "revision.h"
@@ -43,10 +44,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
 
 /*
  * TODO:
- * - Add colors to the graph.
- *   Pick a color for each column, and print all characters
- *   in that column with the specified color.
- *
  * - 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.
@@ -72,11 +69,14 @@ struct column {
 	 */
 	struct commit *commit;
 	/*
-	 * XXX: Once we add support for colors, struct column could also
-	 * contain the color of its branch line.
+	 * The color to (optionally) print this column in.  This is an
+	 * index into column_colors.
 	 */
+	unsigned short color;
 };
 
+#define COLUMN_COLORS_MAX (ARRAY_SIZE(column_colors))
+
 enum graph_state {
 	GRAPH_PADDING,
 	GRAPH_SKIP,
@@ -86,6 +86,39 @@ enum graph_state {
 	GRAPH_COLLAPSING
 };
 
+/*
+ * The list of available column colors.
+ */
+static char column_colors[][COLOR_MAXLEN] = {
+	GIT_COLOR_RED,
+	GIT_COLOR_GREEN,
+	GIT_COLOR_YELLOW,
+	GIT_COLOR_BLUE,
+	GIT_COLOR_MAGENTA,
+	GIT_COLOR_CYAN,
+	GIT_COLOR_BOLD GIT_COLOR_RED,
+	GIT_COLOR_BOLD GIT_COLOR_GREEN,
+	GIT_COLOR_BOLD GIT_COLOR_YELLOW,
+	GIT_COLOR_BOLD GIT_COLOR_BLUE,
+	GIT_COLOR_BOLD GIT_COLOR_MAGENTA,
+	GIT_COLOR_BOLD GIT_COLOR_CYAN,
+};
+
+static const char *column_get_color_code(const struct column *c)
+{
+	return column_colors[c->color];
+}
+
+static void strbuf_write_column(struct strbuf *sb, const struct column *c,
+				char col_char)
+{
+	if (c->color < COLUMN_COLORS_MAX)
+		strbuf_addstr(sb, column_get_color_code(c));
+	strbuf_addch(sb, col_char);
+	if (c->color < COLUMN_COLORS_MAX)
+		strbuf_addstr(sb, GIT_COLOR_RESET);
+}
+
 struct git_graph {
 	/*
 	 * The commit currently being processed
@@ -185,6 +218,11 @@ struct git_graph {
 	 * temporary array each time we have to output a collapsing line.
 	 */
 	int *new_mapping;
+	/*
+	 * The current default column color being used.  This is
+	 * stored as an index into the array column_colors.
+	 */
+	unsigned short default_column_color;
 };
 
 struct git_graph *graph_init(struct rev_info *opt)
@@ -201,6 +239,7 @@ struct git_graph *graph_init(struct rev_info *opt)
 	graph->num_columns = 0;
 	graph->num_new_columns = 0;
 	graph->mapping_size = 0;
+	graph->default_column_color = 0;
 
 	/*
 	 * Allocate a reasonably large default number of columns
@@ -312,6 +351,33 @@ static struct commit_list *first_interesting_parent(struct git_graph *graph)
 	return next_interesting_parent(graph, parents);
 }
 
+unsigned short graph_get_current_column_color(const struct git_graph *graph)
+{
+	if (!DIFF_OPT_TST(&graph->revs->diffopt, COLOR_DIFF))
+		return COLUMN_COLORS_MAX;
+	return graph->default_column_color;
+}
+
+/*
+ * Update the graph's default column color.
+ */
+static void graph_increment_column_color(struct git_graph *graph)
+{
+	graph->default_column_color = (graph->default_column_color + 1) %
+		ARRAY_SIZE(column_colors);
+}
+
+unsigned short graph_find_commit_color(const struct git_graph *graph,
+				       const struct commit *commit)
+{
+	int i;
+	for (i = 0; i < graph->num_columns; i++) {
+		if (graph->columns[i].commit == commit)
+			return graph->columns[i].color;
+	}
+	return graph_get_current_column_color(graph);
+}
+
 static void graph_insert_into_new_columns(struct git_graph *graph,
 					  struct commit *commit,
 					  int *mapping_index)
@@ -334,6 +400,7 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 	 * This commit isn't already in new_columns.  Add it.
 	 */
 	graph->new_columns[graph->num_new_columns].commit = commit;
+	graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit);
 	graph->mapping[*mapping_index] = graph->num_new_columns;
 	*mapping_index += 2;
 	graph->num_new_columns++;
@@ -445,6 +512,12 @@ static void graph_update_columns(struct git_graph *graph)
 			for (parent = first_interesting_parent(graph);
 			     parent;
 			     parent = next_interesting_parent(graph, parent)) {
+				/*
+				 * If this is a merge increment the current
+				 * color.
+				 */
+				if (graph->num_parents > 1)
+					graph_increment_column_color(graph);
 				graph_insert_into_new_columns(graph,
 							      parent->item,
 							      &mapping_idx);
@@ -569,11 +642,11 @@ 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.
 	 */
-	int extra;
-	if (sb->len >= graph->width)
+	int extra, printing;
+	printing = strbuf_count_printing_chars(sb);
+	if (printing >= graph->width)
 		return;
-
-	extra = graph->width - sb->len;
+	extra = graph->width - printing;
 	strbuf_addf(sb, "%*s", (int) extra, "");
 }
 
@@ -596,7 +669,8 @@ 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_addstr(sb, "| ");
+		strbuf_write_column(sb, &graph->new_columns[i], '|');
+		strbuf_addch(sb, ' ');
 	}
 
 	graph_pad_horizontally(graph, sb);
@@ -649,7 +723,8 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		struct column *col = &graph->columns[i];
 		if (col->commit == graph->commit) {
 			seen_this = 1;
-			strbuf_addf(sb, "| %*s", graph->expansion_row, "");
+			strbuf_write_column(sb, col, '|');
+			strbuf_addf(sb, " %*s", graph->expansion_row, "");
 		} else if (seen_this && (graph->expansion_row == 0)) {
 			/*
 			 * This is the first line of the pre-commit output.
@@ -662,14 +737,15 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				strbuf_addstr(sb, "\\ ");
+				strbuf_write_column(sb, col, '\\');
 			else
-				strbuf_addstr(sb, "| ");
+				strbuf_write_column(sb, col, '|');
 		} else if (seen_this && (graph->expansion_row > 0)) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, '\\');
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
 		}
+		strbuf_addch(sb, ' ');
 	}
 
 	graph_pad_horizontally(graph, sb);
@@ -714,10 +790,30 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 	strbuf_addch(sb, '*');
 }
 
+void graph_draw_octopus_merge(const struct git_graph *graph,
+			      struct strbuf *sb)
+{
+	/*
+	 * Here dashless_commits represents the number of parents
+	 * which don't need to have dashes (because their edges fit
+	 * neatly under the commit).
+	 */
+	const int dashless_commits = 2;
+	int col_num, i;
+	int num_dashes =
+		((graph->num_parents - dashless_commits) * 2) - 1;
+	for (i = 0; i < num_dashes; i++) {
+		col_num = (i / 2) + dashless_commits;
+		strbuf_write_column(sb, &graph->new_columns[col_num], '-');
+	}
+	col_num = (i / 2) + dashless_commits;
+	strbuf_write_column(sb, &graph->new_columns[col_num], '.');
+}
+
 static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
-	int i, j;
+	int i;
 
 	/*
 	 * Output the row containing this commit
@@ -728,6 +824,7 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 	 */
 	seen_this = 0;
 	for (i = 0; i <= graph->num_columns; i++) {
+		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
 		if (i == graph->num_columns) {
 			if (seen_this)
@@ -741,17 +838,10 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 			seen_this = 1;
 			graph_output_commit_char(graph, sb);
 
-			if (graph->num_parents < 3)
-				strbuf_addch(sb, ' ');
-			else {
-				int num_dashes =
-					((graph->num_parents - 2) * 2) - 1;
-				for (j = 0; j < num_dashes; j++)
-					strbuf_addch(sb, '-');
-				strbuf_addstr(sb, ". ");
-			}
+			if (graph->num_parents > 3)
+				graph_draw_octopus_merge(graph, sb);
 		} else if (seen_this && (graph->num_parents > 2)) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, '\\');
 		} else if (seen_this && (graph->num_parents == 2)) {
 			/*
 			 * This is a 2-way merge commit.
@@ -768,12 +858,13 @@ 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_addstr(sb, "\\ ");
+				strbuf_write_column(sb, col, '\\');
 			else
-				strbuf_addstr(sb, "| ");
+				strbuf_write_column(sb, col, '|');
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
 		}
+		strbuf_addch(sb, ' ');
 	}
 
 	graph_pad_horizontally(graph, sb);
@@ -789,6 +880,17 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
+struct column *find_new_column_by_commit(struct git_graph *graph,
+					 struct commit *commit)
+{
+	int i;
+	for (i = 0; i < graph->num_new_columns; i++) {
+		if (graph->new_columns[i].commit == commit)
+			return &graph->new_columns[i];
+	}
+	return 0;
+}
+
 static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
@@ -798,24 +900,46 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf
 	 * Output the post-merge row
 	 */
 	for (i = 0; i <= graph->num_columns; i++) {
+		struct column *col = &graph->columns[i];
 		struct commit *col_commit;
 		if (i == graph->num_columns) {
 			if (seen_this)
 				break;
 			col_commit = graph->commit;
 		} else {
-			col_commit = graph->columns[i].commit;
+			col_commit = col->commit;
 		}
 
 		if (col_commit == graph->commit) {
+			/*
+			 * Since the current commit is a merge find
+			 * the columns for the parent commits in
+			 * new_columns and use those to format the
+			 * edges.
+			 */
+			struct commit_list *parents = NULL;
+			struct column *par_column;
 			seen_this = 1;
-			strbuf_addch(sb, '|');
-			for (j = 0; j < graph->num_parents - 1; j++)
-				strbuf_addstr(sb, "\\ ");
+			parents = first_interesting_parent(graph);
+			assert(parents);
+			par_column = find_new_column_by_commit(graph,parents->item);
+			assert(par_column);
+
+			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, ' ');
+			}
 		} else if (seen_this) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, '\\');
+			strbuf_addch(sb, ' ');
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
+			strbuf_addch(sb, ' ');
 		}
 	}
 
@@ -912,9 +1036,11 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 		if (target < 0)
 			strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
-			strbuf_addch(sb, '|');
-		else
-			strbuf_addch(sb, '/');
+			strbuf_write_column(sb, &graph->new_columns[target], '|');
+		else {
+			strbuf_write_column(sb, &graph->new_columns[target], '/');
+
+		}
 	}
 
 	graph_pad_horizontally(graph, sb);
@@ -979,9 +1105,10 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 	 * children that we have already processed.)
 	 */
 	for (i = 0; i < graph->num_columns; i++) {
-		struct commit *col_commit = graph->columns[i].commit;
+		struct column *col = &graph->columns[i];
+		struct commit *col_commit = col->commit;
 		if (col_commit == graph->commit) {
-			strbuf_addch(sb, '|');
+			strbuf_write_column(sb, col, '|');
 
 			if (graph->num_parents < 3)
 				strbuf_addch(sb, ' ');
@@ -991,7 +1118,8 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 					strbuf_addch(sb, ' ');
 			}
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
+			strbuf_addch(sb, ' ');
 		}
 	}
 
diff --git a/strbuf.c b/strbuf.c
index a884960..666460d 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -1,3 +1,4 @@
+#include <ctype.h>
 #include "cache.h"
 #include "refs.h"
 
@@ -138,6 +139,44 @@ void strbuf_list_free(struct strbuf **sbs)
 	free(sbs);
 }
 
+/*
+ * Return the length of the escape sequence in a string buffer
+ * starting at index i.  If there is no escape sequence starting at
+ * return 0.
+ */
+size_t strbuf_esc_sequence_length(const struct strbuf *sb, size_t i)
+{
+	size_t start = i;
+	if (sb->buf[i] != '\033')
+		return 0;
+	++i;
+
+	if (i >= sb->len || sb->buf[i] != '[')
+		return 0;
+	++i;
+	while (i < sb->len && isdigit(sb->buf[i]))
+		++i;
+
+	if (i >= sb->len || sb->buf[i] != 'm')
+		return 0;
+	return i - start;
+}
+
+size_t strbuf_count_printing_chars(const struct strbuf *sb)
+{
+	int i;
+	size_t n = 0;
+	size_t esc_len;
+	for (i = 0; i < sb->len; i++) {
+		esc_len = strbuf_esc_sequence_length(sb, i);
+		if (esc_len)
+			i += esc_len;
+		else if (isgraph(sb->buf[i]) || sb->buf[i] == ' ')
+			++n;
+	}
+	return n;
+}
+
 int strbuf_cmp(const struct strbuf *a, const struct strbuf *b)
 {
 	int len = a->len < b->len ? a->len: b->len;
diff --git a/strbuf.h b/strbuf.h
index 9ee908a..3851ddf 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -86,6 +86,7 @@ extern void strbuf_tolower(struct strbuf *);
 extern struct strbuf **strbuf_split(const struct strbuf *, int delim);
 extern void strbuf_list_free(struct strbuf **);
 
+extern size_t strbuf_count_printing_chars(const struct strbuf *sb);
 /*----- add data in your buffer -----*/
 static inline void strbuf_addch(struct strbuf *sb, int c) {
 	strbuf_grow(sb, 1);
-- 
1.5.6.3

Re: [PATCH v4] graph API: Added logic for colored edges

[Junio C Hamano]

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

> I assumed that the +1 in your example was a typo since AFAIKS ARRAY_SIZE
> should give us one past the last index.

You are correct.

> Also if git is to be expanded allow the use of non-ANSI color codes (or
> already does so) the strbuf_escape_sequence_length needs to be updated
> to accept the relevant escape codes.

Actually, I am starting to hate this.

Just step back a bit and imagine how you would do this, if you _were_
writing an application to do this kind of thing, generating output
directly to the terminal.  You obviously would not seek back and count the
width of what you sent out.  Instead,...?

That's right.  You just keep a running total of how much you sent, iow,
what column you expect the current cursor should be.  Can't we do the same
thing here?

> @@ -312,6 +351,33 @@ static struct commit_list *first_interesting_parent(struct git_graph *graph)
>  	return next_interesting_parent(graph, parents);
>  }
>  
> +unsigned short graph_get_current_column_color(const struct git_graph *graph)

static?

> +static void graph_increment_column_color(struct git_graph *graph)
> +{
> +	graph->default_column_color = (graph->default_column_color + 1) %
> +		ARRAY_SIZE(column_colors);

COLUMN_COLORS_MAX?

> +unsigned short graph_find_commit_color(const struct git_graph *graph,
> +				       const struct commit *commit)
> +{

static?

> @@ -714,10 +790,30 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
>  	strbuf_addch(sb, '*');
>  }
>  
> +void graph_draw_octopus_merge(const struct git_graph *graph,
> +			      struct strbuf *sb)

static?

> @@ -789,6 +880,17 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
>  		graph_update_state(graph, GRAPH_COLLAPSING);
>  }
>  
> +struct column *find_new_column_by_commit(struct git_graph *graph,
> +					 struct commit *commit)
> +{

static?

> diff --git a/strbuf.c b/strbuf.c
> index a884960..666460d 100644
> --- a/strbuf.c
> +++ b/strbuf.c
> @@ -1,3 +1,4 @@
> +#include <ctype.h>
>  #include "cache.h"
>  #include "refs.h"

BAD.  Do not directly include system headers.  If you need isgraph(),
please support it as part of sane_ctype.  But if you count what you
emitted so far, you would not have to do this at all.

> +/*
> + * Return the length of the escape sequence in a string buffer
> + * starting at index i.  If there is no escape sequence starting at
> + * return 0.
> + */
> +size_t strbuf_esc_sequence_length(const struct strbuf *sb, size_t i)
> +{
> +	size_t start = i;
> +	if (sb->buf[i] != '\033')
> +		return 0;
> +	++i;
> +
> +	if (i >= sb->len || sb->buf[i] != '[')
> +		return 0;
> +	++i;
> +	while (i < sb->len && isdigit(sb->buf[i]))
> +		++i;
> +	if (i >= sb->len || sb->buf[i] != 'm')
> +		return 0;

These preincrements are extremely unreadable at least for me.

	if (sb->buf[i++] != '\033')
        	return 0;
	if (sb->len <= i || sb->buf[i++] != '[')
        	return 0;
	...

But again the point is hopefully moot.

[PATCH v5] graph API: Added logic for colored edges

[Allan Caffee]

Modified the graph drawing logic to colorize edges based on parent-child
relationships similiarly to gitk.

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

diff --git a/color.h b/color.h
index 6846be1..18abeb7 100644
--- a/color.h
+++ b/color.h
@@ -11,6 +11,7 @@
 #define GIT_COLOR_GREEN		"\033[32m"
 #define GIT_COLOR_YELLOW	"\033[33m"
 #define GIT_COLOR_BLUE		"\033[34m"
+#define GIT_COLOR_MAGENTA	"\033[35m"
 #define GIT_COLOR_CYAN		"\033[36m"
 #define GIT_COLOR_BG_RED	"\033[41m"
 
diff --git a/graph.c b/graph.c
index 162a516..0fcb61a 100644
--- a/graph.c
+++ b/graph.c
@@ -1,5 +1,6 @@
 #include "cache.h"
 #include "commit.h"
+#include "color.h"
 #include "graph.h"
 #include "diff.h"
 #include "revision.h"
@@ -43,10 +44,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
 
 /*
  * TODO:
- * - Add colors to the graph.
- *   Pick a color for each column, and print all characters
- *   in that column with the specified color.
- *
  * - 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.
@@ -72,9 +69,10 @@ struct column {
 	 */
 	struct commit *commit;
 	/*
-	 * XXX: Once we add support for colors, struct column could also
-	 * contain the color of its branch line.
+	 * The color to (optionally) print this column in.  This is an
+	 * index into column_colors.
 	 */
+	unsigned short color;
 };
 
 enum graph_state {
@@ -86,6 +84,41 @@ enum graph_state {
 	GRAPH_COLLAPSING
 };
 
+/*
+ * The list of available column colors.
+ */
+static char column_colors[][COLOR_MAXLEN] = {
+	GIT_COLOR_RED,
+	GIT_COLOR_GREEN,
+	GIT_COLOR_YELLOW,
+	GIT_COLOR_BLUE,
+	GIT_COLOR_MAGENTA,
+	GIT_COLOR_CYAN,
+	GIT_COLOR_BOLD GIT_COLOR_RED,
+	GIT_COLOR_BOLD GIT_COLOR_GREEN,
+	GIT_COLOR_BOLD GIT_COLOR_YELLOW,
+	GIT_COLOR_BOLD GIT_COLOR_BLUE,
+	GIT_COLOR_BOLD GIT_COLOR_MAGENTA,
+	GIT_COLOR_BOLD GIT_COLOR_CYAN,
+};
+
+#define COLUMN_COLORS_MAX (ARRAY_SIZE(column_colors))
+
+static const char *column_get_color_code(const struct column *c)
+{
+	return column_colors[c->color];
+}
+
+static void strbuf_write_column(struct strbuf *sb, const struct column *c,
+				char col_char)
+{
+	if (c->color < COLUMN_COLORS_MAX)
+		strbuf_addstr(sb, column_get_color_code(c));
+	strbuf_addch(sb, col_char);
+	if (c->color < COLUMN_COLORS_MAX)
+		strbuf_addstr(sb, GIT_COLOR_RESET);
+}
+
 struct git_graph {
 	/*
 	 * The commit currently being processed
@@ -185,6 +218,11 @@ struct git_graph {
 	 * temporary array each time we have to output a collapsing line.
 	 */
 	int *new_mapping;
+	/*
+	 * The current default column color being used.  This is
+	 * stored as an index into the array column_colors.
+	 */
+	unsigned short default_column_color;
 };
 
 struct git_graph *graph_init(struct rev_info *opt)
@@ -201,6 +239,7 @@ struct git_graph *graph_init(struct rev_info *opt)
 	graph->num_columns = 0;
 	graph->num_new_columns = 0;
 	graph->mapping_size = 0;
+	graph->default_column_color = 0;
 
 	/*
 	 * Allocate a reasonably large default number of columns
@@ -312,6 +351,33 @@ static struct commit_list *first_interesting_parent(struct git_graph *graph)
 	return next_interesting_parent(graph, parents);
 }
 
+static unsigned short graph_get_current_column_color(const struct git_graph *graph)
+{
+	if (!DIFF_OPT_TST(&graph->revs->diffopt, COLOR_DIFF))
+		return COLUMN_COLORS_MAX;
+	return graph->default_column_color;
+}
+
+/*
+ * Update the graph's default column color.
+ */
+static void graph_increment_column_color(struct git_graph *graph)
+{
+	graph->default_column_color = (graph->default_column_color + 1) %
+		COLUMN_COLORS_MAX;
+}
+
+static unsigned short graph_find_commit_color(const struct git_graph *graph,
+					      const struct commit *commit)
+{
+	int i;
+	for (i = 0; i < graph->num_columns; i++) {
+		if (graph->columns[i].commit == commit)
+			return graph->columns[i].color;
+	}
+	return graph_get_current_column_color(graph);
+}
+
 static void graph_insert_into_new_columns(struct git_graph *graph,
 					  struct commit *commit,
 					  int *mapping_index)
@@ -334,6 +400,7 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 	 * This commit isn't already in new_columns.  Add it.
 	 */
 	graph->new_columns[graph->num_new_columns].commit = commit;
+	graph->new_columns[graph->num_new_columns].color = graph_find_commit_color(graph, commit);
 	graph->mapping[*mapping_index] = graph->num_new_columns;
 	*mapping_index += 2;
 	graph->num_new_columns++;
@@ -445,6 +512,12 @@ static void graph_update_columns(struct git_graph *graph)
 			for (parent = first_interesting_parent(graph);
 			     parent;
 			     parent = next_interesting_parent(graph, parent)) {
+				/*
+				 * If this is a merge increment the current
+				 * color.
+				 */
+				if (graph->num_parents > 1)
+					graph_increment_column_color(graph);
 				graph_insert_into_new_columns(graph,
 							      parent->item,
 							      &mapping_idx);
@@ -560,7 +633,8 @@ static int graph_is_mapping_correct(struct git_graph *graph)
 	return 1;
 }
 
-static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)
+static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb,
+				   int chars_written)
 {
 	/*
 	 * Add additional spaces to the end of the strbuf, so that all
@@ -570,10 +644,10 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)
 	 * aligned for the entire commit.
 	 */
 	int extra;
-	if (sb->len >= graph->width)
+	if (chars_written >= graph->width)
 		return;
 
-	extra = graph->width - sb->len;
+	extra = graph->width - chars_written;
 	strbuf_addf(sb, "%*s", (int) extra, "");
 }
 
@@ -596,10 +670,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_addstr(sb, "| ");
+		strbuf_write_column(sb, &graph->new_columns[i], '|');
+		strbuf_addch(sb, ' ');
 	}
 
-	graph_pad_horizontally(graph, sb);
+	graph_pad_horizontally(graph, sb, graph->num_new_columns * 2);
 }
 
 static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
@@ -609,7 +684,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);
+	graph_pad_horizontally(graph, sb, 3);
 
 	if (graph->num_parents >= 3 &&
 	    graph->commit_index < (graph->num_columns - 1))
@@ -623,6 +698,7 @@ 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
@@ -645,11 +721,14 @@ 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_addf(sb, "| %*s", graph->expansion_row, "");
+			strbuf_write_column(sb, col, '|');
+			strbuf_addf(sb, " %*s", graph->expansion_row, "");
+			chars_written += 2 + graph->expansion_row;
 		} else if (seen_this && (graph->expansion_row == 0)) {
 			/*
 			 * This is the first line of the pre-commit output.
@@ -662,17 +741,22 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 			 */
 			if (graph->prev_state == GRAPH_POST_MERGE &&
 			    graph->prev_commit_index < i)
-				strbuf_addstr(sb, "\\ ");
+				strbuf_write_column(sb, col, '\\');
 			else
-				strbuf_addstr(sb, "| ");
+				strbuf_write_column(sb, col, '|');
+			chars_written++;
 		} else if (seen_this && (graph->expansion_row > 0)) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, '\\');
+			chars_written++;
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
+			chars_written++;
 		}
+		strbuf_addch(sb, ' ');
+		chars_written++;
 	}
 
-	graph_pad_horizontally(graph, sb);
+	graph_pad_horizontally(graph, sb, chars_written);
 
 	/*
 	 * Increment graph->expansion_row,
@@ -714,10 +798,34 @@ static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
 	strbuf_addch(sb, '*');
 }
 
+/*
+ * Draw an octopus merge and return the number of characters written.
+ */
+static int graph_draw_octopus_merge(struct git_graph *graph,
+				    struct strbuf *sb)
+{
+	/*
+	 * Here dashless_commits represents the number of parents
+	 * which don't need to have dashes (because their edges fit
+	 * neatly under the commit).
+	 */
+	const int dashless_commits = 2;
+	int col_num, i;
+	int num_dashes =
+		((graph->num_parents - dashless_commits) * 2) - 1;
+	for (i = 0; i < num_dashes; i++) {
+		col_num = (i / 2) + dashless_commits;
+		strbuf_write_column(sb, &graph->new_columns[col_num], '-');
+	}
+	col_num = (i / 2) + dashless_commits;
+	strbuf_write_column(sb, &graph->new_columns[col_num], '.');
+	return num_dashes + 1;
+}
+
 static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
-	int i, j;
+	int i, chars_written;
 
 	/*
 	 * Output the row containing this commit
@@ -727,7 +835,9 @@ 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;
 		if (i == graph->num_columns) {
 			if (seen_this)
@@ -740,18 +850,14 @@ 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 < 3)
-				strbuf_addch(sb, ' ');
-			else {
-				int num_dashes =
-					((graph->num_parents - 2) * 2) - 1;
-				for (j = 0; j < num_dashes; j++)
-					strbuf_addch(sb, '-');
-				strbuf_addstr(sb, ". ");
-			}
+			if (graph->num_parents > 3)
+				chars_written += graph_draw_octopus_merge(graph,
+									  sb);
 		} else if (seen_this && (graph->num_parents > 2)) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, '\\');
+			chars_written++;
 		} else if (seen_this && (graph->num_parents == 2)) {
 			/*
 			 * This is a 2-way merge commit.
@@ -768,15 +874,19 @@ 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_addstr(sb, "\\ ");
+				strbuf_write_column(sb, col, '\\');
 			else
-				strbuf_addstr(sb, "| ");
+				strbuf_write_column(sb, col, '|');
+			chars_written++;
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
+			chars_written++;
 		}
+		strbuf_addch(sb, ' ');
+		chars_written++;
 	}
 
-	graph_pad_horizontally(graph, sb);
+	graph_pad_horizontally(graph, sb, chars_written);
 
 	/*
 	 * Update graph->state
@@ -789,37 +899,75 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 		graph_update_state(graph, GRAPH_COLLAPSING);
 }
 
+static struct column *find_new_column_by_commit(struct git_graph *graph,
+						struct commit *commit)
+{
+	int i;
+	for (i = 0; i < graph->num_new_columns; i++) {
+		if (graph->new_columns[i].commit == commit)
+			return &graph->new_columns[i];
+	}
+	return 0;
+}
+
 static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
-	int i, j;
+	int i, j, chars_written;
 
 	/*
 	 * 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;
 		if (i == graph->num_columns) {
 			if (seen_this)
 				break;
 			col_commit = graph->commit;
 		} else {
-			col_commit = graph->columns[i].commit;
+			col_commit = col->commit;
 		}
 
 		if (col_commit == graph->commit) {
+			/*
+			 * Since the current commit is a merge find
+			 * the columns for the parent commits in
+			 * new_columns and use those to format the
+			 * edges.
+			 */
+			struct commit_list *parents = NULL;
+			struct column *par_column;
 			seen_this = 1;
-			strbuf_addch(sb, '|');
-			for (j = 0; j < graph->num_parents - 1; j++)
-				strbuf_addstr(sb, "\\ ");
+			parents = first_interesting_parent(graph);
+			assert(parents);
+			par_column = find_new_column_by_commit(graph,parents->item);
+			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);
+				par_column = find_new_column_by_commit(graph,parents->item);
+				assert(par_column);
+				strbuf_write_column(sb, par_column, '\\');
+				strbuf_addch(sb, ' ');
+			}
+			chars_written += j * 2;
 		} else if (seen_this) {
-			strbuf_addstr(sb, "\\ ");
+			strbuf_write_column(sb, col, '\\');
+			strbuf_addch(sb, ' ');
+			chars_written += 2;
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
+			strbuf_addch(sb, ' ');
+			chars_written += 2;
 		}
 	}
 
-	graph_pad_horizontally(graph, sb);
+	graph_pad_horizontally(graph, sb, chars_written);
 
 	/*
 	 * Update graph->state
@@ -912,12 +1060,12 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 		if (target < 0)
 			strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
-			strbuf_addch(sb, '|');
+			strbuf_write_column(sb, &graph->new_columns[target], '|');
 		else
-			strbuf_addch(sb, '/');
+			strbuf_write_column(sb, &graph->new_columns[target], '/');
 	}
 
-	graph_pad_horizontally(graph, sb);
+	graph_pad_horizontally(graph, sb, graph->mapping_size);
 
 	/*
 	 * Swap mapping and new_mapping
@@ -979,9 +1127,10 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 	 * children that we have already processed.)
 	 */
 	for (i = 0; i < graph->num_columns; i++) {
-		struct commit *col_commit = graph->columns[i].commit;
+		struct column *col = &graph->columns[i];
+		struct commit *col_commit = col->commit;
 		if (col_commit == graph->commit) {
-			strbuf_addch(sb, '|');
+			strbuf_write_column(sb, col, '|');
 
 			if (graph->num_parents < 3)
 				strbuf_addch(sb, ' ');
@@ -991,11 +1140,12 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 					strbuf_addch(sb, ' ');
 			}
 		} else {
-			strbuf_addstr(sb, "| ");
+			strbuf_write_column(sb, col, '|');
+			strbuf_addch(sb, ' ');
 		}
 	}
 
-	graph_pad_horizontally(graph, sb);
+	graph_pad_horizontally(graph, sb, graph->num_columns);
 
 	/*
 	 * Update graph->prev_state since we have output a padding line
-- 
1.5.6.3