[PATCH 1/4] Add history graph API

[PATCH 1/4] Add history graph API

[Adam Simpkins]

This new API allows the commit history to be displayed as a text-based
graphical representation.

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
This is a replacement for the git-graph patch I submitted last weekend.
It adds the graph functionality as a new API.  A subsequent commit
updates "git log" and "git rev-list" to use the new API.

I saw that Jan Engelhardt also submitted a patch for his git-forest
script this past week.  It looks like a fine tool, too.

I think there are benefits to having the graphing functionality built in
to git.  This way all of the existing log functionality (argument
parsing, pretty formats, etc) can be easily re-used.  Other builtin
parts of git can also take advantage of the graphing API.  It is also
one less tool for system administrators to install and maintain
(although this depends on how the distros decide to package things, I
suppose).

I also prefer the output of my graphing API better than that of
git-forest (although, as the author, I'm a bit biased).  It is more
similar to gitk's graph, which many people are already familiar with.
It also doesn't require a terminal with Unicode support.

I do like the fact that git-forest prints the names of the refs that
point to each commit.  For the graphing API, we could perhaps add a "%r"
specifier to --pretty=format to print the refs pointing to the commit.

 Documentation/technical/api-history-graph.txt |  108 ++++
 Makefile                                      |    2 +
 graph.c                                       |  711 +++++++++++++++++++++++++
 graph.h                                       |   57 ++
 4 files changed, 878 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/technical/api-history-graph.txt
 create mode 100644 graph.c
 create mode 100644 graph.h

diff --git a/Documentation/technical/api-history-graph.txt b/Documentation/technical/api-history-graph.txt
new file mode 100644
index 0000000..56a0a1e
--- /dev/null
+++ b/Documentation/technical/api-history-graph.txt
@@ -0,0 +1,108 @@
+history graph API
+=================
+
+The graph API is used to draw a text-based representation of the commit
+history.  The API generates the graph in a line-by-line fashion.
+
+Calling sequence
+----------------
+
+* Create a `struct git_graph` by calling `graph_init()`
+
+* Use the revision walking API to walk through a group of contiguous commits.
+
+* For each commit you walk through, call `graph_update()`.  Then call
+  `graph_next_line()` repeatedly, until `graph_is_commit_finished()` returns
+  non-zero.  Each call go `graph_next_line()` will output a single line of the
+  graph.  The resulting lines will not contain any newlines.
+  `graph_next_line()` returns 1 if the resulting line contains the current
+  commit, or 0 if this is merely a line needed to adjust the graph before or
+  after the current commit.  This return value can be used to determine where
+  to print the commit summary information alongside the graph output.
+
+Data structure
+--------------
+`struct git_graph` is an opaque data type used to store the current graph
+state.
+
+Limitations
+-----------
+
+* `graph_update()` must be called with commits in topological order.  The
+  commits must also be a contiguous group--intervening parents should not
+  be ommitted.  Otherwise, the graph API cannot determine the proper
+  parent-child relationships between the commits.  If intervening parents
+  are ommitted, the next ancestor that is used will appear to be on a
+  separate branch in the graph.
+
+* The graph API does not currently support reverse commit ordering.  In
+  order to implement reverse ordering, the graphing API needs an
+  (efficient) mechanism to find the children of a commit.
+
+Sample usage
+------------
+
+------------
+struct commit *commit;
+struct git_graph *graph = graph_init();
+
+while ((commit = get_revision(opts)) != NULL) {
+	graph_update(graph, commit);
+	while (!graph_is_commit_finished(graph))
+	{
+		struct strbuf sb;
+		int is_commit_line;
+
+		strbuf_init(&sb, 0);
+		is_commit_line = graph_next_line(graph, &sb);
+		fputs(sb.buf, stdout);
+
+		if (is_commit_line)
+			log_tree_commit(opts, commit);
+		else
+			putchar(opts->diffopt.line_termination);
+	}
+}
+
+graph_release(graph);
+------------
+
+Sample output
+-------------
+
+The following is an example of the output from the graph API.  This output does
+not include any commit summary information--callers of responsible for
+outputting that information, if desired.
+
+------------
+*
+*
+M
+|\
+* |
+| | *
+| \ \
+|  \ \
+M-. \ \
+|\ \ \ \
+| | * | |
+| | | | | *
+| | | | | *
+| | | | | M
+| | | | | |\
+| | | | | | *
+| * | | | | |
+| | | | | M  \
+| | | | | |\  |
+| | | | * | | |
+| | | | * | | |
+* | | | | | | |
+| |/ / / / / /
+|/| / / / / /
+* | | | | | |
+|/ / / / / /
+* | | | | |
+| | | | | *
+| | | | |/
+| | | | *
+------------
diff --git a/Makefile b/Makefile
index 7c70b00..3395b59 100644
--- a/Makefile
+++ b/Makefile
@@ -345,6 +345,7 @@ LIB_H += diff.h
 LIB_H += dir.h
 LIB_H += fsck.h
 LIB_H += git-compat-util.h
+LIB_H += graph.h
 LIB_H += grep.h
 LIB_H += hash.h
 LIB_H += list-objects.h
@@ -409,6 +410,7 @@ LIB_OBJS += entry.o
 LIB_OBJS += environment.o
 LIB_OBJS += exec_cmd.o
 LIB_OBJS += fsck.o
+LIB_OBJS += graph.o
 LIB_OBJS += grep.o
 LIB_OBJS += hash.o
 LIB_OBJS += help.o
diff --git a/graph.c b/graph.c
new file mode 100644
index 0000000..d8cb7d4
--- /dev/null
+++ b/graph.c
@@ -0,0 +1,711 @@
+#include "cache.h"
+#include "commit.h"
+#include "graph.h"
+
+/*
+ * 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.
+ *
+ * - 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 {
+	/*
+	 * The parent commit of this column.
+	 */
+	struct commit *commit;
+	/*
+	 * XXX: Once we add support for colors, struct column could also
+	 * contain the color of its branch line.
+	 */
+};
+
+enum graph_state {
+	GRAPH_PADDING,
+	GRAPH_SKIP,
+	GRAPH_PRE_COMMIT,
+	GRAPH_COMMIT,
+	GRAPH_POST_MERGE,
+	GRAPH_COLLAPSING
+};
+
+struct git_graph {
+	/*
+	 * The commit currently being processed
+	 */
+	struct commit *commit;
+	/*
+	 * The number of parents this commit has.
+	 * (Stored so we don't have to walk over them each time we need
+	 * this number)
+	 */
+	int num_parents;
+	/*
+	 * The next expansion row to print
+	 * when state is GRAPH_PRE_COMMIT
+	 */
+	int expansion_row;
+	/*
+	 * The current output state.
+	 * This tells us what kind of line graph_next_line() should output.
+	 */
+	enum graph_state state;
+	/*
+	 * The maximum number of columns that can be stored in the columns
+	 * and new_columns arrays.  This is also half the number of entries
+	 * that can be stored in the mapping and new_mapping arrays.
+	 */
+	int column_capacity;
+	/*
+	 * The number of columns (also called "branch lines" in some places)
+	 */
+	int num_columns;
+	/*
+	 * The number of columns in the new_columns array
+	 */
+	int num_new_columns;
+	/*
+	 * The number of entries in the mapping array
+	 */
+	int mapping_size;
+	/*
+	 * The column state before we output the current commit.
+	 */
+	struct column *columns;
+	/*
+	 * The new column state after we output the current commit.
+	 * Only valid when state is GRAPH_COLLAPSING.
+	 */
+	struct column *new_columns;
+	/*
+	 * An array that tracks the current state of each
+	 * character in the output line during state GRAPH_COLLAPSING.
+	 * Each entry is -1 if this character is empty, or a non-negative
+	 * integer if the character contains a branch line.  The value of
+	 * the integer indicates the target position for this branch line.
+	 * (I.e., this array maps the current column positions to their
+	 * desired positions.)
+	 *
+	 * The maximum capacity of this array is always
+	 * sizeof(int) * 2 * column_capacity.
+	 */
+	int *mapping;
+	/*
+	 * A temporary array for computing the next mapping state
+	 * while we are outputting a mapping line.  This is stored as part
+	 * of the git_graph simply so we don't have to allocate a new
+	 * temporary array each time we have to output a collapsing line.
+	 */
+	int *new_mapping;
+};
+
+struct git_graph *graph_init()
+{
+	struct git_graph *graph = xmalloc(sizeof(struct git_graph));
+	graph->commit = NULL;
+	graph->num_parents = 0;
+	graph->expansion_row = 0;
+	graph->state = GRAPH_PADDING;
+	graph->num_columns = 0;
+	graph->num_new_columns = 0;
+	graph->mapping_size = 0;
+
+	/*
+	 * Allocate a reasonably large default number of columns
+	 * We'll automatically grow columns later if we need more room.
+	 */
+	graph->column_capacity = 30;
+	graph->columns = xmalloc(sizeof(struct column) *
+				 graph->column_capacity);
+	graph->new_columns = xmalloc(sizeof(struct column) *
+				     graph->column_capacity);
+	graph->mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity);
+	graph->new_mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity);
+
+	return graph;
+}
+
+void graph_release(struct git_graph *graph)
+{
+	free(graph->columns);
+	free(graph->new_columns);
+	free(graph->mapping);
+	free(graph);
+}
+
+static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
+{
+	if (graph->column_capacity >= num_columns)
+		return;
+
+	do {
+		graph->column_capacity *= 2;
+	} while (graph->column_capacity < num_columns);
+
+	graph->columns = xrealloc(graph->columns,
+				  sizeof(struct column) *
+				  graph->column_capacity);
+	graph->new_columns = xrealloc(graph->new_columns,
+				      sizeof(struct column) *
+				      graph->column_capacity);
+	graph->mapping = xrealloc(graph->mapping,
+				  sizeof(int) * 2 * graph->column_capacity);
+	graph->new_mapping = xrealloc(graph->new_mapping,
+				      sizeof(int) * 2 * graph->column_capacity);
+}
+
+static void graph_insert_into_new_columns(struct git_graph *graph,
+					  struct commit *commit,
+					  int mapping_index)
+{
+	int i;
+
+	/*
+	 * If the commit is already in the new_columns list, we don't need to
+	 * add it.  Just update the mapping correctly.
+	 */
+	for (i = 0; i < graph->num_new_columns; ++i) {
+		if (graph->new_columns[i].commit == commit) {
+			graph->mapping[mapping_index] = i;
+			return;
+		}
+	}
+
+	/*
+	 * This commit isn't already in new_columns.  Add it.
+	 */
+	graph->new_columns[graph->num_new_columns].commit = commit;
+	graph->mapping[mapping_index] = graph->num_new_columns;
+	++graph->num_new_columns;
+}
+
+static void graph_update_columns(struct git_graph *graph)
+{
+	struct commit_list *parent;
+	struct column *tmp_columns;
+	int max_new_columns;
+	int mapping_idx;
+	int i, seen_this;
+
+	/*
+	 * Swap graph->columns with graph->new_columns
+	 * graph->columns contains the state for the previous commit,
+	 * and new_columns now contains the state for our commit.
+	 *
+	 * We'll re-use the old columns array as storage to compute the new
+	 * columns list for the commit after this one.
+	 */
+	tmp_columns = graph->columns;
+	graph->columns = graph->new_columns;
+	graph->num_columns = graph->num_new_columns;
+
+	graph->new_columns = tmp_columns;
+	graph->num_new_columns = 0;
+
+	/*
+	 * Now update new_columns and mapping with the information for the
+	 * commit after this one.
+	 *
+	 * First, make sure we have enough room.  At most, there will
+	 * be graph->num_columns + graph->num_parents columns for the next
+	 * commit.
+	 */
+	max_new_columns = graph->num_columns + graph->num_parents;
+	graph_ensure_capacity(graph, max_new_columns);
+
+	/*
+	 * Clear out graph->mapping
+	 */
+	graph->mapping_size = 2 * max_new_columns;
+	for (i = 0; i < graph->mapping_size; ++i)
+		graph->mapping[i] = -1;
+
+	/*
+	 * Populate graph->new_columns and graph->mapping
+	 *
+	 * Some of the parents of this commit may already be in
+	 * graph->columns.  If so, graph->new_columns should only contain a
+	 * single entry for each such commit.  graph->mapping should
+	 * contain information about where each current branch line is
+	 * supposed to end up after the collapsing is performed.
+	 */
+	seen_this = 0;
+	mapping_idx = 0;
+	for (i = 0; i <= graph->num_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;
+		}
+
+		if (col_commit == graph->commit) {
+			seen_this = 1;
+			for (parent = graph->commit->parents;
+			     parent;
+			     parent = parent->next) {
+				graph_insert_into_new_columns(graph,
+							      parent->item,
+							      mapping_idx);
+				mapping_idx += 2;
+			}
+		} else {
+			graph_insert_into_new_columns(graph, col_commit,
+						      mapping_idx);
+			mapping_idx += 2;
+		}
+	}
+
+	/*
+	 * Shrink mapping_size to be the minimum necessary
+	 */
+	while (graph->mapping_size > 1 &&
+	       graph->mapping[graph->mapping_size - 1] < 0)
+		--graph->mapping_size;
+}
+
+void graph_update(struct git_graph *graph, struct commit *commit)
+{
+	struct commit_list *parent;
+
+	/*
+	 * Set the new commit
+	 */
+	graph->commit = commit;
+
+	/*
+	 * Count how many parents this commit has
+	 */
+	graph->num_parents = 0;
+	for (parent = commit->parents; parent; parent = parent->next)
+		++(graph->num_parents);
+
+	/*
+	 * Call graph_update_columns() to update
+	 * columns, new_columns, and mapping.
+	 */
+	graph_update_columns(graph);
+
+	graph->expansion_row = 0;
+
+	/*
+	 * Update graph->state.
+	 *
+	 * If the previous commit didn't get to the GRAPH_PADDING state,
+	 * it never finished its output.  Goto GRAPH_SKIP, to print out
+	 * a line to indicate that portion of the graph is missing.
+	 *
+	 * Otherwise, if there are 3 or more parents, we need to print
+	 * extra rows before the commit, to expand the branch lines around
+	 * it and make room for it.
+	 *
+	 * If there are less than 3 parents, we can immediately print the
+	 * commit line.
+	 */
+	if (graph->state != GRAPH_PADDING)
+		graph->state = GRAPH_SKIP;
+	else if (graph->num_parents >= 3)
+		graph->state = GRAPH_PRE_COMMIT;
+	else
+		graph->state = GRAPH_COMMIT;
+}
+
+static int graph_is_mapping_correct(struct git_graph *graph)
+{
+	int i;
+
+	/*
+	 * The mapping is up to date if each entry is at its target,
+	 * or is 1 greater than its target.
+	 * (If it is 1 greater than the target, '/' will be printed, so it
+	 * will look correct on the next row.)
+	 */
+	for (i = 0; i < graph->mapping_size; ++i) {
+		int target = graph->mapping[i];
+		if (target < 0)
+			continue;
+		if (target == (i / 2))
+			continue;
+		return 0;
+	}
+
+	return 1;
+}
+
+static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)
+{
+	/*
+	 * Add additional spaces to the end of the strbuf, so that all
+	 * lines for a particular commit have the same width.
+	 *
+	 * This way, fields printed to the right of the graph will remain
+	 * aligned for the entire commit.
+	 *
+	 * This computation results in 3 extra space to the right in most
+	 * cases, but only 1 extra space if the commit doesn't have any
+	 * children that have already been displayed in the graph (i.e.,
+	 * if the current commit isn't in graph->columns).
+	 */
+	size_t extra;
+	size_t final_width = graph->num_columns + graph->num_parents;
+	if (graph->num_parents < 1)
+		++final_width;
+	final_width *= 2;
+
+	if (sb->len >= final_width)
+		return;
+
+	extra = final_width - sb->len;
+	strbuf_addf(sb, "%*s", extra, "");
+}
+
+static void graph_output_padding_line(struct git_graph *graph,
+				      struct strbuf *sb)
+{
+	int i;
+
+	/*
+	 * We could conceivable be called with a NULL commit
+	 * if our caller has a bug, and invokes graph_next_line()
+	 * immediately after graph_init(), without first calling
+	 * graph_update().  Return without outputting anything in this
+	 * case.
+	 */
+	if (!graph->commit)
+		return;
+
+	/*
+	 * Output a padding row, that leaves all branch lines unchanged
+	 */
+	for (i = 0; i < graph->num_new_columns; ++i) {
+		strbuf_addstr(sb, "| ");
+	}
+
+	graph_pad_horizontally(graph, sb);
+}
+
+static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)
+{
+	/*
+	 * Output an ellipsis to indicate that a portion
+	 * of the graph is missing.
+	 */
+	strbuf_addstr(sb, "...");
+	graph_pad_horizontally(graph, sb);
+
+	if (graph->num_parents >= 3)
+		graph->state = GRAPH_PRE_COMMIT;
+	else
+		graph->state = GRAPH_COMMIT;
+}
+
+static void graph_output_pre_commit_line(struct git_graph *graph,
+					 struct strbuf *sb)
+{
+	int num_expansion_rows;
+	int i, seen_this;
+
+	/*
+	 * This function formats a row that increases the space around a commit
+	 * with multiple parents, to make room for it.  It should only be
+	 * called when there are 3 or more parents.
+	 *
+	 * We need 2 extra rows for every parent over 2.
+	 */
+	assert(graph->num_parents >= 3);
+	num_expansion_rows = (graph->num_parents - 2) * 2;
+
+	/*
+	 * graph->expansion_row tracks the current expansion row we are on.
+	 * It should be in the range [0, num_expansion_rows - 1]
+	 */
+	assert(0 <= graph->expansion_row &&
+	       graph->expansion_row < num_expansion_rows);
+
+	/*
+	 * Output the row
+	 */
+	seen_this = 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, "");
+		} else if (seen_this) {
+			strbuf_addstr(sb, "\\ ");
+		} else {
+			strbuf_addstr(sb, "| ");
+		}
+	}
+
+	graph_pad_horizontally(graph, sb);
+
+	/*
+	 * Increment graph->expansion_row,
+	 * and move to state GRAPH_COMMIT if necessary
+	 */
+	++graph->expansion_row;
+	if (graph->expansion_row >= num_expansion_rows)
+		graph->state = GRAPH_COMMIT;
+}
+
+void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
+{
+	int seen_this = 0;
+	int i, j;
+
+	/*
+	 * Output the row containing this commit
+	 * Iterate up to and including graph->num_columns,
+	 * since the current commit may not be in any of the existing
+	 * columns.  (This happens when the current commit doesn't have any
+	 * children that we have already processed.)
+	 */
+	seen_this = 0;
+	for (i = 0; i <= graph->num_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;
+		}
+
+		if (col_commit == graph->commit) {
+			seen_this = 1;
+			if (graph->num_parents > 1)
+				strbuf_addch(sb, 'M');
+			else
+				strbuf_addch(sb, '*');
+
+			if (graph->num_parents < 2)
+				strbuf_addch(sb, ' ');
+			else if (graph->num_parents == 2)
+				strbuf_addstr(sb, "  ");
+			else {
+				int num_dashes =
+					((graph->num_parents - 2) * 2) - 1;
+				for (j = 0; j < num_dashes; ++j)
+					strbuf_addch(sb, '-');
+				strbuf_addstr(sb, ". ");
+			}
+		} else if (seen_this && (graph->num_parents > 1)) {
+			strbuf_addstr(sb, "\\ ");
+		} else {
+			strbuf_addstr(sb, "| ");
+		}
+	}
+
+	graph_pad_horizontally(graph, sb);
+
+	/*
+	 * Update graph->state
+	 */
+	if (graph->num_parents > 1)
+		graph->state = GRAPH_POST_MERGE;
+	else if (graph_is_mapping_correct(graph))
+		graph->state = GRAPH_PADDING;
+	else
+		graph->state = GRAPH_COLLAPSING;
+}
+
+void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
+{
+	int seen_this = 0;
+	int i, j;
+
+	/*
+	 * Output the post-merge row
+	 */
+	for (i = 0; i <= graph->num_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;
+		}
+
+		if (col_commit == graph->commit) {
+			seen_this = 1;
+			strbuf_addch(sb, '|');
+			for (j = 0; j < graph->num_parents - 1; ++j)
+				strbuf_addstr(sb, "\\ ");
+			if (graph->num_parents == 2)
+				strbuf_addch(sb, ' ');
+		} else if (seen_this && (graph->num_parents > 2)) {
+			strbuf_addstr(sb, "\\ ");
+		} else {
+			strbuf_addstr(sb, "| ");
+		}
+	}
+
+	graph_pad_horizontally(graph, sb);
+
+	/*
+	 * Update graph->state
+	 */
+	if (graph_is_mapping_correct(graph))
+		graph->state = GRAPH_PADDING;
+	else
+		graph->state = GRAPH_COLLAPSING;
+}
+
+void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
+{
+	int i;
+	int *tmp_mapping;
+
+	/*
+	 * Clear out the new_mapping array
+	 */
+	for (i = 0; i < graph->mapping_size; ++i)
+		graph->new_mapping[i] = -1;
+
+	for (i = 0; i < graph->mapping_size; ++i) {
+		int target = graph->mapping[i];
+		if (target < 0)
+			continue;
+
+		/*
+		 * Since update_columns() always inserts the leftmost
+		 * column first, each branch's target location should
+		 * always be either its current location or to the left of
+		 * its current location.
+		 *
+		 * We never have to move branches to the right.  This makes
+		 * the graph much more legible, since whenever branches
+		 * cross, only one is moving directions.
+		 */
+		assert(target * 2 <= i);
+
+		if (target * 2 == i) {
+			/*
+			 * This column is already in the
+			 * correct place
+			 */
+			assert(graph->new_mapping[i] == -1);
+			graph->new_mapping[i] = target;
+		} else if (graph->new_mapping[i - 1] < 0) {
+			/*
+			 * Nothing is to the left.
+			 * Move to the left by one
+			 */
+			graph->new_mapping[i - 1] = target;
+		} else if (graph->new_mapping[i - 1] == target) {
+			/*
+			 * There is a branch line to our left
+			 * already, and it is our target.  We
+			 * combine with this line, since we share
+			 * the same parent commit.
+			 *
+			 * We don't have to add anything to the
+			 * output or new_mapping, since the
+			 * existing branch line has already taken
+			 * care of it.
+			 */
+		} else {
+			/*
+			 * There is a branch line to our left,
+			 * but it isn't our target.  We need to
+			 * cross over it.
+			 *
+			 * The space just to the left of this
+			 * branch should always be empty.
+			 */
+			assert(graph->new_mapping[i - 1] > target);
+			assert(graph->new_mapping[i - 2] < 0);
+			graph->new_mapping[i - 2] = target;
+		}
+	}
+
+	/*
+	 * The new mapping may be 1 smaller than the old mapping
+	 */
+	if (graph->new_mapping[graph->mapping_size - 1] < 0)
+		--graph->mapping_size;
+
+	/*
+	 * Output out a line based on the new mapping info
+	 */
+	for (i = 0; i < graph->mapping_size; ++i) {
+		int target = graph->new_mapping[i];
+		if (target < 0)
+			strbuf_addch(sb, ' ');
+		else if (target * 2 == i)
+			strbuf_addch(sb, '|');
+		else
+			strbuf_addch(sb, '/');
+	}
+
+	graph_pad_horizontally(graph, sb);
+
+	/*
+	 * Swap mapping and new_mapping
+	 */
+	tmp_mapping = graph->mapping;
+	graph->mapping = graph->new_mapping;
+	graph->new_mapping = tmp_mapping;
+
+	/*
+	 * If graph->mapping indicates that all of the branch lines
+	 * are already in the correct positions, we are done.
+	 * Otherwise, we need to collapse some branch lines together.
+	 */
+	if (graph_is_mapping_correct(graph))
+		graph->state = GRAPH_PADDING;
+}
+
+int graph_next_line(struct git_graph *graph, struct strbuf *sb)
+{
+	switch (graph->state) {
+	case GRAPH_PADDING:
+		graph_output_padding_line(graph, sb);
+		return 0;
+	case GRAPH_SKIP:
+		graph_output_skip_line(graph, sb);
+		return 0;
+	case GRAPH_PRE_COMMIT:
+		graph_output_pre_commit_line(graph, sb);
+		return 0;
+	case GRAPH_COMMIT:
+		graph_output_commit_line(graph, sb);
+		return 1;
+	case GRAPH_POST_MERGE:
+		graph_output_post_merge_line(graph, sb);
+		return 0;
+	case GRAPH_COLLAPSING:
+		graph_output_collapsing_line(graph, sb);
+		return 0;
+	}
+
+	assert(0);
+	return 0;
+}
+
+int graph_is_commit_finished(struct git_graph const *graph)
+{
+	return (graph->state == GRAPH_PADDING);
+}
diff --git a/graph.h b/graph.h
new file mode 100644
index 0000000..fc23bf2
--- /dev/null
+++ b/graph.h
@@ -0,0 +1,57 @@
+#ifndef GRAPH_H
+#define GRAPH_H
+
+/* A graph is a pointer to this opaque structure */
+struct git_graph;
+
+/* Defined in commit.h */
+struct commit;
+/* Defined in strbuf.h */
+struct strbuf;
+
+/*
+ * Create a new struct git_graph.
+ * The graph should be freed with graph_release() when no longer needed.
+ */
+struct git_graph *graph_init();
+
+/*
+ * Destroy a struct git_graph and free associated memory.
+ */
+void graph_release(struct git_graph *graph);
+
+/*
+ * Update a git_graph with a new commit.
+ * This will cause the graph to begin outputting lines for the new commit
+ * the next time graph_next_line() is called.
+ *
+ * If graph_update() is called before graph_is_commit_finished() returns 1,
+ * the next call to graph_next_line() will output an ellipsis ("...")
+ * to indicate that a portion of the graph is missing.
+ */
+void graph_update(struct git_graph *graph, struct commit *commit);
+
+/*
+ * Output the next line for a graph.
+ * This formats the next graph line into the specified strbuf.  It is not
+ * terminated with a newline.
+ *
+ * Returns 1 if the line includes the current commit, and 0 otherwise.
+ * graph_next_line() will return 1 exactly once for each time
+ * graph_update() is called.
+ */
+int graph_next_line(struct git_graph *graph, struct strbuf *sb);
+
+/*
+ * Determine if a graph has finished outputting lines for the current
+ * commit.
+ *
+ * Returns 1 if graph_next_line() needs to be called again before
+ * graph_update() should be called.  Returns 0 if no more lines are needed
+ * for this commit.  If 0 is returned, graph_next_line() may still be
+ * called without calling graph_update(), and it will merely output
+ * appropriate "vertical padding" in the graph.
+ */
+int graph_is_commit_finished(struct git_graph const *graph);
+
+#endif /* GRAPH_H */
-- 
1.5.3.6

[PATCH 2/4] graph API: Added additional utility functions to the graph API

[Adam Simpkins]

Added several graph_show_* functions that print directly to stdout instead
of to a strbuf.  Also added functions for explicitly adding vertical padding
in the graph.

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
 Documentation/technical/api-history-graph.txt |   28 +++++
 graph.c                                       |  140 +++++++++++++++++++++++++
 graph.h                                       |   51 +++++++++
 3 files changed, 219 insertions(+), 0 deletions(-)

diff --git a/Documentation/technical/api-history-graph.txt b/Documentation/technical/api-history-graph.txt
index 56a0a1e..34f45b0 100644
--- a/Documentation/technical/api-history-graph.txt
+++ b/Documentation/technical/api-history-graph.txt
@@ -20,6 +20,34 @@ Calling sequence
   after the current commit.  This return value can be used to determine where
   to print the commit summary information alongside the graph output.
 
+Utility functions
+-----------------
+
+The following functions are wrappers around `graph_next_line()` and
+`graph_is_commit_finished()`.  They always print the output to stdout.
+They can all be called with a NULL graph argument, in which case no graph output
+will be printed.
+
+* `graph_show_commit()` calls `graph_next_line()` until it returns non-zero.
+  This prints all graph lines up to, and including, the line containing this
+  commit.  Output is printed to stdout.  The last line printed does not contain
+  a terminating newline.  This should not be called if the commit line has
+  already been printed, or it will loop forever.
+
+* `graph_show_oneline()` calls `graph_next_line()` and prints the result to
+  stdout.  The line printed does not contain a terminating newline.
+
+* `graph_show_remainder()` calls `graph_next_line()` until
+  `graph_is_commit_finished()` returns non-zero.  Output is printed to stdout.
+  The last line printed does not contain a terminating newline.  Returns 1 if
+  output was printed, and 0 if no output was necessary.
+
+* `graph_show_strbuf()` prints the specified strbuf to stdout, prefixing all
+  lines but the first with a graph line.  The caller is responsible for ensuring
+  graph output for the first line has already been printed to stdout.  (This can
+  be done with `graph_show_commit()` or `graph_show_oneline()`.)  If a NULL
+  graph is supplied, the strbuf is printed as-is.
+
 Data structure
 --------------
 `struct git_graph` is an opaque data type used to store the current graph
diff --git a/graph.c b/graph.c
index d8cb7d4..e6d1d3a 100644
--- a/graph.c
+++ b/graph.c
@@ -705,7 +705,147 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 	return 0;
 }
 
+void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
+{
+	int i, j;
+
+	if (graph->state != GRAPH_COMMIT) {
+		graph_next_line(graph, sb);
+		return;
+	}
+
+	/*
+	 * Output the row containing this commit
+	 * Iterate up to and including graph->num_columns,
+	 * since the current commit may not be in any of the existing
+	 * columns.  (This happens when the current commit doesn't have any
+	 * children that we have already processed.)
+	 */
+	for (i = 0; i < graph->num_columns; ++i) {
+		struct commit *col_commit = graph->columns[i].commit;
+		if (col_commit == graph->commit) {
+			strbuf_addch(sb, '|');
+
+			if (graph->num_parents < 3)
+				strbuf_addch(sb, ' ');
+			else {
+				int num_spaces = ((graph->num_parents - 2) * 2);
+				for (j = 0; j < num_spaces; ++j)
+					strbuf_addch(sb, ' ');
+			}
+		} else {
+			strbuf_addstr(sb, "| ");
+		}
+	}
+
+	graph_pad_horizontally(graph, sb);
+}
+
 int graph_is_commit_finished(struct git_graph const *graph)
 {
 	return (graph->state == GRAPH_PADDING);
 }
+
+void graph_show_commit(struct git_graph *graph)
+{
+	struct strbuf msgbuf;
+	int shown_commit_line = 0;
+
+	if (!graph)
+		return;
+
+	strbuf_init(&msgbuf, 0);
+
+	while (!shown_commit_line) {
+		shown_commit_line = graph_next_line(graph, &msgbuf);
+		fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
+		if (!shown_commit_line)
+			putchar('\n');
+		strbuf_setlen(&msgbuf, 0);
+	}
+
+	strbuf_release(&msgbuf);
+}
+
+void graph_show_oneline(struct git_graph *graph)
+{
+	struct strbuf msgbuf;
+
+	if (!graph)
+		return;
+
+	strbuf_init(&msgbuf, 0);
+	graph_next_line(graph, &msgbuf);
+	fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
+	strbuf_release(&msgbuf);
+}
+
+void graph_show_padding(struct git_graph *graph)
+{
+	struct strbuf msgbuf;
+
+	if (!graph)
+		return;
+
+	strbuf_init(&msgbuf, 0);
+	graph_padding_line(graph, &msgbuf);
+	fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
+	strbuf_release(&msgbuf);
+}
+
+int graph_show_remainder(struct git_graph *graph)
+{
+	struct strbuf msgbuf;
+	int shown = 0;
+
+	if (!graph)
+		return 0;
+
+	if (graph_is_commit_finished(graph))
+		return 0;
+
+	strbuf_init(&msgbuf, 0);
+	for (;;) {
+		graph_next_line(graph, &msgbuf);
+		fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
+		strbuf_setlen(&msgbuf, 0);
+		shown = 1;
+
+		if (!graph_is_commit_finished(graph))
+			putchar('\n');
+		else
+			break;
+	}
+	strbuf_release(&msgbuf);
+
+	return shown;
+}
+
+
+void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
+{
+	if (!graph) {
+		fwrite(sb->buf, sizeof(char), sb->len, stdout);
+		return;
+	}
+
+	/*
+	 * Print the strbuf line by line,
+	 * and display the graph info before each line but the first.
+	 */
+	char *p = sb->buf;
+	while (p) {
+		size_t len;
+		char *next_p = strchr(p, '\n');
+		if (next_p) {
+			next_p++;
+			len = next_p - p;
+		} else {
+			len = (sb->buf + sb->len) - p;
+		}
+		fwrite(p, sizeof(char), len, stdout);
+		if (next_p && *next_p != '\0')
+			graph_show_oneline(graph);
+		p = next_p;
+	}
+}
diff --git a/graph.h b/graph.h
index fc23bf2..817862e 100644
--- a/graph.h
+++ b/graph.h
@@ -43,6 +43,15 @@ void graph_update(struct git_graph *graph, struct commit *commit);
 int graph_next_line(struct git_graph *graph, struct strbuf *sb);
 
 /*
+ * Output a padding line in the graph.
+ * This is similar to graph_next_line().  However, it is guaranteed to
+ * never print the current commit line.  Instead, if the commit line is
+ * next, it will simply output a line of vertical padding, extending the
+ * branch lines downwards, but leaving them otherwise unchanged.
+ */
+void graph_padding_line(struct git_graph *graph, struct strbuf *sb);
+
+/*
  * Determine if a graph has finished outputting lines for the current
  * commit.
  *
@@ -54,4 +63,46 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb);
  */
 int graph_is_commit_finished(struct git_graph const *graph);
 
+
+/*
+ * graph_show_*: helper functions for printing to stdout
+ */
+
+
+/*
+ * If the graph is non-NULL, print the history graph to stdout,
+ * up to and including the line containing this commit.
+ * Does not print a terminating newline on the last line.
+ */
+void graph_show_commit(struct git_graph *graph);
+
+/*
+ * If the graph is non-NULL, print one line of the history graph to stdout.
+ * Does not print a terminating newline on the last line.
+ */
+void graph_show_oneline(struct git_graph *graph);
+
+/*
+ * If the graph is non-NULL, print one line of vertical graph padding to
+ * stdout.  Does not print a terminating newline on the last line.
+ */
+void graph_show_padding(struct git_graph *graph);
+
+/*
+ * If the graph is non-NULL, print the rest of the history graph for this
+ * commit to stdout.  Does not print a terminating newline on the last line.
+ */
+int graph_show_remainder(struct git_graph *graph);
+
+/*
+ * Print a strbuf to stdout.  If the graph is non-NULL, all lines but the
+ * first will be prefixed with the graph output.
+ *
+ * Since the firat line will not include the graph ouput, the caller is
+ * responsible for printing this line's graph (perhaps via
+ * graph_show_commit() or graph_show_oneline()) before calling
+ * graph_show_strbuf().
+ */
+void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
+
 #endif /* GRAPH_H */
-- 
1.5.3.6

[PATCH 3/4] git log and git rev-list: Add --graph option

[Adam Simpkins]

The --graph option causes a text-based representation of the history
graph to be printed on the left-hand side of the output.

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
The --graph option can be used with any --pretty format.  If this change
is too intrusive for people's liking, a smaller change could probably be
done that only adds --pretty=graph and --pretty=graph:<user_fmt>
options.

At the moment, --graph and --reverse are mutually exclusive.  With
Junio's new --children patch for git log, it probably shouldn't be too
hard to get them working together.

 Documentation/technical/api-history-graph.txt |   61 +++++++++++++++++------
 builtin-rev-list.c                            |   50 +++++++++++++++++--
 log-tree.c                                    |   65 +++++++++++++++++++++++--
 revision.c                                    |   28 ++++++++++-
 revision.h                                    |    3 +
 5 files changed, 180 insertions(+), 27 deletions(-)

diff --git a/Documentation/technical/api-history-graph.txt b/Documentation/technical/api-history-graph.txt
index 34f45b0..c5f9054 100644
--- a/Documentation/technical/api-history-graph.txt
+++ b/Documentation/technical/api-history-graph.txt
@@ -4,26 +4,34 @@ history graph API
 The graph API is used to draw a text-based representation of the commit
 history.  The API generates the graph in a line-by-line fashion.
 
-Calling sequence
-----------------
+Functions
+---------
 
-* Create a `struct git_graph` by calling `graph_init()`
+Core functions:
 
-* Use the revision walking API to walk through a group of contiguous commits.
+* `graph_init()` creates a new `struct git_graph`
+
+* `graph_release()` destroys a `struct git_graph`, and frees the memory
+  associated with it.
 
-* For each commit you walk through, call `graph_update()`.  Then call
-  `graph_next_line()` repeatedly, until `graph_is_commit_finished()` returns
-  non-zero.  Each call go `graph_next_line()` will output a single line of the
-  graph.  The resulting lines will not contain any newlines.
-  `graph_next_line()` returns 1 if the resulting line contains the current
-  commit, or 0 if this is merely a line needed to adjust the graph before or
-  after the current commit.  This return value can be used to determine where
-  to print the commit summary information alongside the graph output.
+* `graph_update()` moves the graph to a new commit.
 
-Utility functions
------------------
+* `graph_next_line()` outputs the next line of the graph into a strbuf.  It does
+  not add a terminating newline.
 
-The following functions are wrappers around `graph_next_line()` and
+* `graph_padding_line()` outputs a line of vertical padding in the graph.  It
+  is similar to `graph_next_line()`, but is guaranteed to never print the line
+  containing the current commit.  Where `graph_next_line()` would print the
+  commit line next, `graph_padding_line()` prints a line that simply extends
+  all branch lines downwards one row, leaving their positions unchanged.
+
+* `graph_is_commit_finished()` determines if the graph has output all lines
+  necessary for the current commit.  If `graph_update()` is called before all
+  lines for the current commit have been printed, the next call to
+  `graph_next_line()` will output an ellipsis, to indicate that a portion of the
+  graph was omitted.
+
+The following utility functions are wrappers around `graph_next_line()` and
 `graph_is_commit_finished()`.  They always print the output to stdout.
 They can all be called with a NULL graph argument, in which case no graph output
 will be printed.
@@ -37,6 +45,9 @@ will be printed.
 * `graph_show_oneline()` calls `graph_next_line()` and prints the result to
   stdout.  The line printed does not contain a terminating newline.
 
+* `graph_show_padding()` calls `graph_padding_line()` and prints the result to
+  stdout.  The line printed does not contain a terminating newline.
+
 * `graph_show_remainder()` calls `graph_next_line()` until
   `graph_is_commit_finished()` returns non-zero.  Output is printed to stdout.
   The last line printed does not contain a terminating newline.  Returns 1 if
@@ -53,6 +64,26 @@ Data structure
 `struct git_graph` is an opaque data type used to store the current graph
 state.
 
+Calling sequence
+----------------
+
+* Create a `struct git_graph` by calling `graph_init()`.  When using the
+  revision walking API, this is done automatically by `setup_revisions()` if
+  the '--graph' option is supplied.
+
+* Use the revision walking API to walk through a group of contiguous commits.
+  The `get_revision()` function automatically calls `graph_update()` each time
+  it is invoked.
+
+* For each commit, call `graph_next_line()` repeatedly, until
+  `graph_is_commit_finished()` returns non-zero.  Each call go
+  `graph_next_line()` will output a single line of the graph.  The resulting
+  lines will not contain any newlines.  `graph_next_line()` returns 1 if the
+  resulting line contains the current commit, or 0 if this is merely a line
+  needed to adjust the graph before or after the current commit.  This return
+  value can be used to determine where to print the commit summary information
+  alongside the graph output.
+
 Limitations
 -----------
 
diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index edc0bd3..4427caa 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -10,6 +10,7 @@
 #include "list-objects.h"
 #include "builtin.h"
 #include "log-tree.h"
+#include "graph.h"
 
 /* bits #0-15 in revision.h */
 
@@ -58,6 +59,8 @@ static const char *header_prefix;
 static void finish_commit(struct commit *commit);
 static void show_commit(struct commit *commit)
 {
+	graph_show_commit(revs.graph);
+
 	if (show_timestamp)
 		printf("%lu ", commit->date);
 	if (header_prefix)
@@ -85,20 +88,55 @@ static void show_commit(struct commit *commit)
 		}
 	}
 	show_decorations(commit);
-	if (revs.commit_format == CMIT_FMT_ONELINE)
-		putchar(' ');
-	else
-		putchar('\n');
 
 	if (revs.verbose_header && commit->buffer) {
 		struct strbuf buf;
+
+		if (revs.commit_format == CMIT_FMT_ONELINE) {
+			putchar(' ');
+		} else {
+			putchar('\n');
+			graph_show_oneline(revs.graph);
+		}
+
 		strbuf_init(&buf, 0);
 		pretty_print_commit(revs.commit_format, commit,
 				    &buf, revs.abbrev, NULL, NULL,
 				    revs.date_mode, 0);
-		if (buf.len)
-			printf("%s%c", buf.buf, hdr_termination);
+		if (buf.len) {
+			if (revs.graph) {
+				graph_show_strbuf(revs.graph, &buf);
+				 if (revs.commit_format == CMIT_FMT_ONELINE) {
+					 /*
+					  * For CMIT_FMT_ONELINE, the buffer
+					  * doesn't end in a newline, so add one
+					  * first if graph_show_remainder()
+					  * needs to print more lines.
+					  */
+					if (!graph_is_commit_finished(revs.graph)) {
+						putchar('\n');
+						graph_show_remainder(revs.graph);
+					}
+				} else {
+					/*
+					 * For other formats, we want at least
+					 * one line separating commits.  If
+					 * graph_show_remainder() doesn't print
+					 * anything, add a padding line.
+					 */
+					if (!graph_show_remainder(revs.graph))
+						graph_show_padding(revs.graph);
+				}
+			} else {
+				fwrite(buf.buf, sizeof(char), buf.len, stdout);
+			}
+			putchar(hdr_termination);
+		}
 		strbuf_release(&buf);
+	} else {
+		putchar('\n');
+		if (graph_show_remainder(revs.graph))
+			putchar('\n');
 	}
 	maybe_flush_or_die(stdout, "stdout");
 	finish_commit(commit);
diff --git a/log-tree.c b/log-tree.c
index 5b29639..5b78d1b 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -1,6 +1,7 @@
 #include "cache.h"
 #include "diff.h"
 #include "commit.h"
+#include "graph.h"
 #include "log-tree.h"
 #include "reflog-walk.h"
 
@@ -221,6 +222,8 @@ void show_log(struct rev_info *opt, const char *sep)
 
 	opt->loginfo = NULL;
 	if (!opt->verbose_header) {
+		graph_show_commit(opt->graph);
+
 		if (commit->object.flags & BOUNDARY)
 			putchar('-');
 		else if (commit->object.flags & UNINTERESTING)
@@ -235,6 +238,10 @@ void show_log(struct rev_info *opt, const char *sep)
 		if (opt->parents)
 			show_parents(commit, abbrev_commit);
 		show_decorations(commit);
+		if (opt->graph && !graph_is_commit_finished(opt->graph)) {
+			putchar('\n');
+			graph_show_remainder(opt->graph);
+		}
 		putchar(opt->diffopt.line_termination);
 		return;
 	}
@@ -251,11 +258,19 @@ void show_log(struct rev_info *opt, const char *sep)
 	extra = "";
 	if (*sep != '\n' && opt->commit_format == CMIT_FMT_ONELINE)
 		extra = "\n";
-	if (opt->shown_one && opt->commit_format != CMIT_FMT_ONELINE)
+	if (opt->shown_one && opt->commit_format != CMIT_FMT_ONELINE) {
+		graph_show_padding(opt->graph);
 		putchar(opt->diffopt.line_termination);
+	}
 	opt->shown_one = 1;
 
 	/*
+	 * If the history graph was requested,
+	 * print the graph, up to this commit's line
+	 */
+	graph_show_commit(opt->graph);
+
+	/*
 	 * Print header line of header..
 	 */
 
@@ -287,8 +302,19 @@ void show_log(struct rev_info *opt, const char *sep)
 						  abbrev_commit));
 		show_decorations(commit);
 		printf("%s", diff_get_color_opt(&opt->diffopt, DIFF_RESET));
-		putchar(opt->commit_format == CMIT_FMT_ONELINE ? ' ' : '\n');
+		if (opt->commit_format == CMIT_FMT_ONELINE) {
+			putchar(' ');
+		} else {
+			putchar('\n');
+			graph_show_oneline(opt->graph);
+		}
 		if (opt->reflog_info) {
+			/*
+			 * setup_revisions() ensures that opt->reflog_info
+			 * and opt->graph cannot both be set,
+			 * so we don't need to worry about printing the
+			 * graph info here.
+			 */
 			show_reflog_message(opt->reflog_info,
 				    opt->commit_format == CMIT_FMT_ONELINE,
 				    opt->date_mode);
@@ -314,11 +340,40 @@ void show_log(struct rev_info *opt, const char *sep)
 
 	if (opt->add_signoff)
 		append_signoff(&msgbuf, opt->add_signoff);
-	if (opt->show_log_size)
+	if (opt->show_log_size) {
 		printf("log size %i\n", (int)msgbuf.len);
+		graph_show_oneline(opt->graph);
+	}
 
-	if (msgbuf.len)
-		printf("%s%s%s", msgbuf.buf, extra, sep);
+	if (msgbuf.len) {
+		if (opt->graph) {
+			graph_show_strbuf(opt->graph, &msgbuf);
+			if (opt->commit_format == CMIT_FMT_ONELINE) {
+				/*
+				 * For CMIT_FMT_ONELINE, the buffer doesn't
+				 * end in a newline, so add one first if
+				 * graph_show_remainder() needs to print
+				 * more lines.
+				 */
+				if (!graph_is_commit_finished(opt->graph)) {
+					putchar('\n');
+					graph_show_remainder(opt->graph);
+				}
+			} else {
+				/*
+				 * For other formats, we want at least one
+				 * line separating commits.  If
+				 * graph_show_remainder() doesn't print
+				 * anything, add a padding line.
+				 */
+				if (graph_show_remainder(opt->graph))
+					putchar('\n');
+			}
+		} else {
+			fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
+		}
+		printf("%s%s", extra, sep);
+	}
 	strbuf_release(&msgbuf);
 }
 
diff --git a/revision.c b/revision.c
index 196fedc..6c9622c 100644
--- a/revision.c
+++ b/revision.c
@@ -6,6 +6,7 @@
 #include "diff.h"
 #include "refs.h"
 #include "revision.h"
+#include "graph.h"
 #include "grep.h"
 #include "reflog-walk.h"
 #include "patch-ids.h"
@@ -1201,6 +1202,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 				revs->commit_format = get_commit_format(arg+8);
 				continue;
 			}
+			if (!prefixcmp(arg, "--graph")) {
+				revs->topo_order = 1;
+				revs->graph = graph_init();
+				continue;
+			}
 			if (!strcmp(arg, "--root")) {
 				revs->show_root_diff = 1;
 				continue;
@@ -1395,6 +1401,18 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 	if (revs->reverse && revs->reflog_info)
 		die("cannot combine --reverse with --walk-reflogs");
 
+	/*
+	 * Limitations on the graph functionality
+	 */
+	if (revs->reverse && revs->graph)
+		die("cannot combine --reverse with --graph");
+
+	if (revs->reflog_info && revs->graph)
+		die("cannot combine --walk-reflogs with --graph");
+
+	if (revs->graph && revs->prune_data)
+		die("cannot use --graph when pruning commit list");
+
 	return left;
 }
 
@@ -1596,7 +1614,7 @@ static void gc_boundary(struct object_array *array)
 	}
 }
 
-struct commit *get_revision(struct rev_info *revs)
+static struct commit *get_revision_internal(struct rev_info *revs)
 {
 	struct commit *c = NULL;
 	struct commit_list *l;
@@ -1703,3 +1721,11 @@ struct commit *get_revision(struct rev_info *revs)
 
 	return c;
 }
+
+struct commit *get_revision(struct rev_info *revs)
+{
+	struct commit *c = get_revision_internal(revs);
+	if (c && revs->graph)
+		graph_update(revs->graph, c);
+	return c;
+}
diff --git a/revision.h b/revision.h
index c8b3b94..d06b991 100644
--- a/revision.h
+++ b/revision.h
@@ -87,6 +87,9 @@ struct rev_info {
 	/* Filter by commit log message */
 	struct grep_opt	*grep_filter;
 
+	/* Display history graph */
+	struct git_graph *graph;
+
 	/* special limits */
 	int skip_count;
 	int max_count;
-- 
1.5.3.6

[PATCH 4/4] git log: Updated --graph to work even when the commit list is pruned

[Adam Simpkins]

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
 graph.c    |   22 +++++++++++++++-------
 revision.c |    3 ---
 2 files changed, 15 insertions(+), 10 deletions(-)

diff --git a/graph.c b/graph.c
index e6d1d3a..be4000f 100644
--- a/graph.c
+++ b/graph.c
@@ -1,6 +1,8 @@
 #include "cache.h"
 #include "commit.h"
 #include "graph.h"
+#include "diff.h"
+#include "revision.h"
 
 /*
  * TODO:
@@ -174,17 +176,24 @@ static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
 
 static void graph_insert_into_new_columns(struct git_graph *graph,
 					  struct commit *commit,
-					  int mapping_index)
+					  int *mapping_index)
 {
 	int i;
 
 	/*
+	 * Ignore uinteresting and pruned commits
+	 */
+	if (commit->object.flags & (UNINTERESTING | TREESAME))
+		return;
+
+	/*
 	 * If the commit is already in the new_columns list, we don't need to
 	 * add it.  Just update the mapping correctly.
 	 */
 	for (i = 0; i < graph->num_new_columns; ++i) {
 		if (graph->new_columns[i].commit == commit) {
-			graph->mapping[mapping_index] = i;
+			graph->mapping[*mapping_index] = i;
+			*mapping_index += 2;
 			return;
 		}
 	}
@@ -193,7 +202,8 @@ 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->mapping[mapping_index] = graph->num_new_columns;
+	graph->mapping[*mapping_index] = graph->num_new_columns;
+	*mapping_index += 2;
 	++graph->num_new_columns;
 }
 
@@ -266,13 +276,11 @@ static void graph_update_columns(struct git_graph *graph)
 			     parent = parent->next) {
 				graph_insert_into_new_columns(graph,
 							      parent->item,
-							      mapping_idx);
-				mapping_idx += 2;
+							      &mapping_idx);
 			}
 		} else {
 			graph_insert_into_new_columns(graph, col_commit,
-						      mapping_idx);
-			mapping_idx += 2;
+						      &mapping_idx);
 		}
 	}
 
diff --git a/revision.c b/revision.c
index 6c9622c..6a1f513 100644
--- a/revision.c
+++ b/revision.c
@@ -1410,9 +1410,6 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 	if (revs->reflog_info && revs->graph)
 		die("cannot combine --walk-reflogs with --graph");
 
-	if (revs->graph && revs->prune_data)
-		die("cannot use --graph when pruning commit list");
-
 	return left;
 }
 
-- 
1.5.3.6

Re: [PATCH 1/4] Add history graph API

[Teemu Likonen]

Adam Simpkins kirjoitti:

> I think there are benefits to having the graphing functionality built
> in to git.  This way all of the existing log functionality (argument
> parsing, pretty formats, etc) can be easily re-used.  Other builtin
> parts of git can also take advantage of the graphing API. 

I don't know anything about the inside stuff but from user's point of 
view this is the kind of text-based graph I'd agree to be integrated to 
Git (well, I integrated it already to my Git). I like this a lot, 
thanks.

Maybe git-doc.txt should be updated with new option(s)?

Re: [PATCH 1/4] Add history graph API

[Johannes Schindelin]

Hi,

On Sun, 6 Apr 2008, Adam Simpkins wrote:

> I do like the fact that git-forest prints the names of the refs that 
> point to each commit.  For the graphing API, we could perhaps add a "%r" 
> specifier to --pretty=format to print the refs pointing to the commit.

Would "--decorate" help?

Ciao,
Dscho

Re: [PATCH 1/4] Add history graph API

[Johannes Schindelin]

Hi,

On Sun, 6 Apr 2008, Adam Simpkins wrote:

> diff --git a/graph.h b/graph.h
> new file mode 100644
> index 0000000..fc23bf2
> --- /dev/null
> +++ b/graph.h
> @@ -0,0 +1,57 @@
> +#ifndef GRAPH_H
> +#define GRAPH_H
> +
> +/* A graph is a pointer to this opaque structure */
> +struct git_graph;
> +
> +/* Defined in commit.h */
> +struct commit;
> +/* Defined in strbuf.h */
> +struct strbuf;

You do not need those.

Apart from that, it looks very, very clean to me.  (Except maybe the 
prefix ++ that could have been a postfix ++ in the line before, but that 
is just me.)

Ciao,
Dscho

Re: [PATCH 3/4] git log and git rev-list: Add --graph option

[Teemu Likonen]

Adam Simpkins kirjoitti:

> The --graph option causes a text-based representation of the history
> graph to be printed on the left-hand side of the output.

The '--graph' seems to work nicely with every '--pretty=' option 
except 'email'.

$ git log --graph --pretty=email


|
M     From 77ad7a49d3cc946487ca759e5361effbcfb03be5 [...]
From: Junio C Hamano <gitster@pobox.com>
|\    Date: Fri, 4 Apr 2008 22:38:32 -0700
| |   Subject: [PATCH] Merge git://repo.or.cz/git-gui
| |   
| |   * git://repo.or.cz/git-gui:
| |     git-gui: use +/- instead of ]/[ to show [...]
| |     git-gui: Update french translation
| |     git-gui: Switch keybindings for [ and ] to [...]


The 'From:' field is always at the column 1.

[PATCH] bash: Add command line completion of --graph (git log)

[Teemu Likonen]

Signed-off-by: Teemu Likonen <tlikonen@iki.fi>
---
 contrib/completion/git-completion.bash |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 791e30f..cd26d0c 100755
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -754,6 +754,7 @@ _git_log ()
 			--pretty= --name-status --name-only --raw
 			--not --all
 			--left-right --cherry-pick
+			--graph
 			"
 		return
 		;;
-- 
1.5.5-rc3.GIT

Re: [PATCH 1/4] Add history graph API

[Adam Simpkins]

On Sun, Apr 06, 2008 at 11:30:16PM +0300, Teemu Likonen wrote:
> 
> Maybe git-doc.txt should be updated with new option(s)?

Ah, you're right, I forgot about that.  I'll send out a new patch to
update Documentation/rev-list-options.txt

-- 
Adam Simpkins
adam@adamsimpkins.net

[PATCH 5/5] Document the new --graph option for log and rev-list

[Adam Simpkins]

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
 Documentation/rev-list-options.txt |   10 ++++++++++
 1 files changed, 10 insertions(+), 0 deletions(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 2648a55..ce6a101 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -75,6 +75,16 @@ you would get an output line this:
 	-xxxxxxx... 1st on a
 -----------------------------------------------------------------------
 
+--graph::
+
+	Draw a text-based graphical representation of the commit history
+	on the left hand side of the output.  This may cause extra lines
+	to be printed in between commits, in order for the graph history
+	to be drawn properly.
++
+This implies the '--topo-order' option by default, but the
+'--date-order' option may also be specified.
+
 Diff Formatting
 ~~~~~~~~~~~~~~~
 
-- 
1.5.3.6

Re: [PATCH 1/4] Add history graph API

[Adam Simpkins]

On Sun, Apr 06, 2008 at 10:06:24PM +0100, Johannes Schindelin wrote:
> 
> On Sun, 6 Apr 2008, Adam Simpkins wrote:
> 
> > +/* Defined in commit.h */
> > +struct commit;
> > +/* Defined in strbuf.h */
> > +struct strbuf;
> 
> You do not need those.

I added them so that graph.h can be included without including any
other header files first.  They can be taken out if we assume that all
users of graph.h will include commit.h and strbuf.h first.

> Apart from that, it looks very, very clean to me.  (Except maybe the 
> prefix ++ that could have been a postfix ++ in the line before, but that 
> is just me.)

Sorry, force of habit.  I tried to remember to use postfix in most
places, but I guess I forgot in that place.

I do most of my programming in C++, which allows crazy things like
defining prefix and postfix ++ and -- operators on classes.  When
using these on classes, the prefix operator is normally more efficient
than the postfix version, so I'm just in the habit of using prefix
increment everywhere.  This can easily be changed if postfix is
preferred for the git coding style.

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH 1/4] Add history graph API

[Johannes Schindelin]

Hi,

On Sun, 6 Apr 2008, Adam Simpkins wrote:

> On Sun, Apr 06, 2008 at 10:06:24PM +0100, Johannes Schindelin wrote:
> > 
> > On Sun, 6 Apr 2008, Adam Simpkins wrote:
> > 
> > > +/* Defined in commit.h */
> > > +struct commit;
> > > +/* Defined in strbuf.h */
> > > +struct strbuf;
> > 
> > You do not need those.
> 
> I added them so that graph.h can be included without including any other 
> header files first.  They can be taken out if we assume that all users 
> of graph.h will include commit.h and strbuf.h first.

AFAICT you do not even need them then.  Using "struct strbuf *" without 
ever declaring struct strbuf before that is perfectly valid.

Ciao,
Dscho

Re: [PATCH 1/4] Add history graph API

[Adam Simpkins]

On Sun, Apr 06, 2008 at 09:42:20PM +0100, Johannes Schindelin wrote:
> Hi,
> 
> On Sun, 6 Apr 2008, Adam Simpkins wrote:
> 
> > I do like the fact that git-forest prints the names of the refs that 
> > point to each commit.  For the graphing API, we could perhaps add a "%r" 
> > specifier to --pretty=format to print the refs pointing to the commit.
> 
> Would "--decorate" help?

Yes, it does.  Unfortunately, it doesn't have any effect with
--pretty=format.


Actually, going back and testing this, it looks like I have a bug when
handling --graph together with --pretty=format.  There's a missing
newline after the user's format message and the next graph line.  I'll
try to fix this and submit a patch later this evening.

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH 3/4] git log and git rev-list: Add --graph option

[Adam Simpkins]

On Mon, Apr 07, 2008 at 12:15:32AM +0300, Teemu Likonen wrote:
> Adam Simpkins kirjoitti:
> 
> > The --graph option causes a text-based representation of the history
> > graph to be printed on the left-hand side of the output.
> 
> The '--graph' seems to work nicely with every '--pretty=' option 
> except 'email'.
> 
> $ git log --graph --pretty=email

Yep, I forgot to test that one.  Thanks for pointing it out.
It looks like it shouldn't be too hard to fix.  I'll try to fix it and
submit a patch later this evening.

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH 1/4] Add history graph API

[Adam Simpkins]

On Sun, Apr 06, 2008 at 11:15:58PM +0100, Johannes Schindelin wrote:
> On Sun, 6 Apr 2008, Adam Simpkins wrote:
> > On Sun, Apr 06, 2008 at 10:06:24PM +0100, Johannes Schindelin wrote:
> > > On Sun, 6 Apr 2008, Adam Simpkins wrote:
> > > 
> > > > +/* Defined in commit.h */
> > > > +struct commit;
> > > > +/* Defined in strbuf.h */
> > > > +struct strbuf;
> > > 
> > > You do not need those.
> > 
> > I added them so that graph.h can be included without including any other 
> > header files first.  They can be taken out if we assume that all users 
> > of graph.h will include commit.h and strbuf.h first.
> 
> AFAICT you do not even need them then.  Using "struct strbuf *" without 
> ever declaring struct strbuf before that is perfectly valid.

Trying to compile the following test code with gcc 4.1.2 results in a
warning.

test.c:
	#include <stdio.h>
	
	void test(struct strbuf *sb);
	int main(int argc, char **argv)
	{
		test(NULL);
		return 0;
	}

$ gcc -c test.c
test.c:3: warning: ‘struct strbuf’ declared inside parameter list
test.c:3: warning: its scope is only this definition or declaration, which is probably not what you want

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH 1/4] Add history graph API

[Junio C Hamano]

Adam Simpkins <adam@adamsimpkins.net> writes:

> On Sun, Apr 06, 2008 at 10:06:24PM +0100, Johannes Schindelin wrote:
>> 
>> On Sun, 6 Apr 2008, Adam Simpkins wrote:
>> 
>> > +/* Defined in commit.h */
>> > +struct commit;
>> > +/* Defined in strbuf.h */
>> > +struct strbuf;
>> 
>> You do not need those.
>
> I added them so that graph.h can be included without including any
> other header files first.  They can be taken out if we assume that all
> users of graph.h will include commit.h and strbuf.h first.

The current practice is we expect .c files to include necessary .h files
themselves and avoid including .h files from others (I do not personally
necessarily agree with this practice, by the way, but that is the way it
is).  So please drop them.

> Sorry, force of habit.  I tried to remember to use postfix in most
> places, but I guess I forgot in that place.

We seem to consistently use postfix when increment is done only for its
side effect.

Re: [PATCH 1/4] Add history graph API

[Teemu Likonen]

Adam Simpkins kirjoitti:

> Actually, going back and testing this, it looks like I have a bug
> when handling --graph together with --pretty=format.  There's a
> missing newline after the user's format message and the next graph
> line.  I'll try to fix this and submit a patch later this evening.

Also, the output is not indented for options that display some 
additional information to commit message. Those include:

--raw
--stat
--numstat
--shortstat
--summary
--name-only
--name-status

I'm not sure if the diff output of -p, -u etc. should be 
indented--probably not--but for different stat and summary options it 
would be nice to not have their output displayed over the graph area. 
Especially --name-status is funny since it displays "M" to column 1 to 
indicate modified file while "M" also means merge commit in the graph.

Re: [PATCH 1/4] Add history graph API

[Teemu Likonen]

Adam Simpkins kirjoitti (6.4.2008 klo 11.42):

> [...] graphing API [...] is more similar to gitk's graph, which many
> people are already familiar with. It also doesn't require a terminal
> with Unicode support.

As I've spent some time in testing the --graph functionality I'm
spamming my discoveries here.

When limiting the log output to a subdirectory or to a file the graph
becomes quite hard to understand. Probably the easiest way to
demonstrate my point is to compare side by side (for example)

  git log --graph --pretty=oneline -- Documentation/
 
and

  gitk -- Documentation/

in the Git repository. gitk draws lines between commits even when they
are not in direct parent-child relationship (i.e. there is longer series
of commits between them). With log --graph it's hard to tell which
development line some commits come from.

The whole-repository log graphs seem to work nicely though.

[PATCH 1/4] graph API: Fixed coding style problems

[Adam Simpkins]

- Removed pre-declarations of structs from graph.h; all users are
  expected to include the necessary header files first.
- Replaced prefix increment and decrement operators with postfix
  operators

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
 graph.c |   42 +++++++++++++++++++++---------------------
 graph.h |    5 -----
 2 files changed, 21 insertions(+), 26 deletions(-)

diff --git a/graph.c b/graph.c
index be4000f..6f99063 100644
--- a/graph.c
+++ b/graph.c
@@ -190,7 +190,7 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 	 * If the commit is already in the new_columns list, we don't need to
 	 * add it.  Just update the mapping correctly.
 	 */
-	for (i = 0; i < graph->num_new_columns; ++i) {
+	for (i = 0; i < graph->num_new_columns; i++) {
 		if (graph->new_columns[i].commit == commit) {
 			graph->mapping[*mapping_index] = i;
 			*mapping_index += 2;
@@ -204,7 +204,7 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 	graph->new_columns[graph->num_new_columns].commit = commit;
 	graph->mapping[*mapping_index] = graph->num_new_columns;
 	*mapping_index += 2;
-	++graph->num_new_columns;
+	graph->num_new_columns++;
 }
 
 static void graph_update_columns(struct git_graph *graph)
@@ -245,7 +245,7 @@ static void graph_update_columns(struct git_graph *graph)
 	 * Clear out graph->mapping
 	 */
 	graph->mapping_size = 2 * max_new_columns;
-	for (i = 0; i < graph->mapping_size; ++i)
+	for (i = 0; i < graph->mapping_size; i++)
 		graph->mapping[i] = -1;
 
 	/*
@@ -259,7 +259,7 @@ static void graph_update_columns(struct git_graph *graph)
 	 */
 	seen_this = 0;
 	mapping_idx = 0;
-	for (i = 0; i <= graph->num_columns; ++i) {
+	for (i = 0; i <= graph->num_columns; i++) {
 		struct commit *col_commit;
 		if (i == graph->num_columns) {
 			if (seen_this)
@@ -289,7 +289,7 @@ static void graph_update_columns(struct git_graph *graph)
 	 */
 	while (graph->mapping_size > 1 &&
 	       graph->mapping[graph->mapping_size - 1] < 0)
-		--graph->mapping_size;
+		graph->mapping_size--;
 }
 
 void graph_update(struct git_graph *graph, struct commit *commit)
@@ -306,7 +306,7 @@ void graph_update(struct git_graph *graph, struct commit *commit)
 	 */
 	graph->num_parents = 0;
 	for (parent = commit->parents; parent; parent = parent->next)
-		++(graph->num_parents);
+		graph->num_parents++;
 
 	/*
 	 * Call graph_update_columns() to update
@@ -348,7 +348,7 @@ static int graph_is_mapping_correct(struct git_graph *graph)
 	 * (If it is 1 greater than the target, '/' will be printed, so it
 	 * will look correct on the next row.)
 	 */
-	for (i = 0; i < graph->mapping_size; ++i) {
+	for (i = 0; i < graph->mapping_size; i++) {
 		int target = graph->mapping[i];
 		if (target < 0)
 			continue;
@@ -377,7 +377,7 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)
 	size_t extra;
 	size_t final_width = graph->num_columns + graph->num_parents;
 	if (graph->num_parents < 1)
-		++final_width;
+		final_width++;
 	final_width *= 2;
 
 	if (sb->len >= final_width)
@@ -405,7 +405,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) {
+	for (i = 0; i < graph->num_new_columns; i++) {
 		strbuf_addstr(sb, "| ");
 	}
 
@@ -454,7 +454,7 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 	 * Output the row
 	 */
 	seen_this = 0;
-	for (i = 0; i < graph->num_columns; ++i) {
+	for (i = 0; i < graph->num_columns; i++) {
 		struct column *col = &graph->columns[i];
 		if (col->commit == graph->commit) {
 			seen_this = 1;
@@ -472,7 +472,7 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 	 * Increment graph->expansion_row,
 	 * and move to state GRAPH_COMMIT if necessary
 	 */
-	++graph->expansion_row;
+	graph->expansion_row++;
 	if (graph->expansion_row >= num_expansion_rows)
 		graph->state = GRAPH_COMMIT;
 }
@@ -490,7 +490,7 @@ void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 	 * children that we have already processed.)
 	 */
 	seen_this = 0;
-	for (i = 0; i <= graph->num_columns; ++i) {
+	for (i = 0; i <= graph->num_columns; i++) {
 		struct commit *col_commit;
 		if (i == graph->num_columns) {
 			if (seen_this)
@@ -514,7 +514,7 @@ void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 			else {
 				int num_dashes =
 					((graph->num_parents - 2) * 2) - 1;
-				for (j = 0; j < num_dashes; ++j)
+				for (j = 0; j < num_dashes; j++)
 					strbuf_addch(sb, '-');
 				strbuf_addstr(sb, ". ");
 			}
@@ -546,7 +546,7 @@ void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 	/*
 	 * Output the post-merge row
 	 */
-	for (i = 0; i <= graph->num_columns; ++i) {
+	for (i = 0; i <= graph->num_columns; i++) {
 		struct commit *col_commit;
 		if (i == graph->num_columns) {
 			if (seen_this)
@@ -559,7 +559,7 @@ void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)
 		if (col_commit == graph->commit) {
 			seen_this = 1;
 			strbuf_addch(sb, '|');
-			for (j = 0; j < graph->num_parents - 1; ++j)
+			for (j = 0; j < graph->num_parents - 1; j++)
 				strbuf_addstr(sb, "\\ ");
 			if (graph->num_parents == 2)
 				strbuf_addch(sb, ' ');
@@ -589,10 +589,10 @@ void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
 	/*
 	 * Clear out the new_mapping array
 	 */
-	for (i = 0; i < graph->mapping_size; ++i)
+	for (i = 0; i < graph->mapping_size; i++)
 		graph->new_mapping[i] = -1;
 
-	for (i = 0; i < graph->mapping_size; ++i) {
+	for (i = 0; i < graph->mapping_size; i++) {
 		int target = graph->mapping[i];
 		if (target < 0)
 			continue;
@@ -653,12 +653,12 @@ void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)
 	 * The new mapping may be 1 smaller than the old mapping
 	 */
 	if (graph->new_mapping[graph->mapping_size - 1] < 0)
-		--graph->mapping_size;
+		graph->mapping_size--;
 
 	/*
 	 * Output out a line based on the new mapping info
 	 */
-	for (i = 0; i < graph->mapping_size; ++i) {
+	for (i = 0; i < graph->mapping_size; i++) {
 		int target = graph->new_mapping[i];
 		if (target < 0)
 			strbuf_addch(sb, ' ');
@@ -729,7 +729,7 @@ void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 	 * columns.  (This happens when the current commit doesn't have any
 	 * children that we have already processed.)
 	 */
-	for (i = 0; i < graph->num_columns; ++i) {
+	for (i = 0; i < graph->num_columns; i++) {
 		struct commit *col_commit = graph->columns[i].commit;
 		if (col_commit == graph->commit) {
 			strbuf_addch(sb, '|');
@@ -738,7 +738,7 @@ void graph_padding_line(struct git_graph *graph, struct strbuf *sb)
 				strbuf_addch(sb, ' ');
 			else {
 				int num_spaces = ((graph->num_parents - 2) * 2);
-				for (j = 0; j < num_spaces; ++j)
+				for (j = 0; j < num_spaces; j++)
 					strbuf_addch(sb, ' ');
 			}
 		} else {
diff --git a/graph.h b/graph.h
index 817862e..c1f6892 100644
--- a/graph.h
+++ b/graph.h
@@ -4,11 +4,6 @@
 /* A graph is a pointer to this opaque structure */
 struct git_graph;
 
-/* Defined in commit.h */
-struct commit;
-/* Defined in strbuf.h */
-struct strbuf;
-
 /*
  * Create a new struct git_graph.
  * The graph should be freed with graph_release() when no longer needed.
-- 
1.5.3.6

[PATCH 2/4] log and rev-list: Fixed newline termination issues with --graph

[Adam Simpkins]

Previously, the --graph option had problems when used together with
--pretty=format.  The output was missing a newline at the end of each
entry, before the next graph line.

This change updates the code to treat CMIT_FMT_USERFORMAT just like
CMIT_FMT_ONELINE, even when --graph is not in use.  Like
CMIT_FMT_ONELINE, the pretty_print_commit() output for
CMIT_FMT_USERFORMAT lacks a terminating newline.  Similarly, there
should be no blank line between entries for CMIT_FMT_USERFORMAT.

The old code took care of these cases for CMIT_FMT_ONELINE, but not for
CMIT_FMT_USERFORMAT.  For CMIT_FMT_USERFORMAT, show_log() left each
entry without a terminating newline.  The next call to show_log() would
then try to print an extra blank line between entries.  However, since
the previous entry lacked a newline, the "blank line" simply added a
newline at the end of the previous entry.  For the most part, this made
the output look correct.  The very last entry in the output was always
missing a terminating newline, but piping the output through less would
hide this fact.  (Running with --no-pager would clearly show the missing
newline at the end of the output.)

I believe the old behavior was accidental, rather than intentional.  The
new code always prints a newline at the end of the last entry.

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
 builtin-rev-list.c |   52 ++++++++++++++---------------
 graph.c            |   93 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 graph.h            |   20 ++++++++++-
 log-tree.c         |   61 ++++++++++++++-------------------
 4 files changed, 163 insertions(+), 63 deletions(-)

diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index 4427caa..ac6a6f9 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -53,7 +53,6 @@ static struct rev_info revs;
 
 static int bisect_list;
 static int show_timestamp;
-static int hdr_termination;
 static const char *header_prefix;
 
 static void finish_commit(struct commit *commit);
@@ -103,34 +102,34 @@ static void show_commit(struct commit *commit)
 		pretty_print_commit(revs.commit_format, commit,
 				    &buf, revs.abbrev, NULL, NULL,
 				    revs.date_mode, 0);
-		if (buf.len) {
-			if (revs.graph) {
-				graph_show_strbuf(revs.graph, &buf);
-				 if (revs.commit_format == CMIT_FMT_ONELINE) {
-					 /*
-					  * For CMIT_FMT_ONELINE, the buffer
-					  * doesn't end in a newline, so add one
-					  * first if graph_show_remainder()
-					  * needs to print more lines.
-					  */
-					if (!graph_is_commit_finished(revs.graph)) {
-						putchar('\n');
-						graph_show_remainder(revs.graph);
-					}
-				} else {
-					/*
-					 * For other formats, we want at least
-					 * one line separating commits.  If
-					 * graph_show_remainder() doesn't print
-					 * anything, add a padding line.
-					 */
-					if (!graph_show_remainder(revs.graph))
-						graph_show_padding(revs.graph);
-				}
+		if (revs.graph) {
+			/*
+			 * If revs.graph is non-NULL, we always need to print
+			 * an extra newline, even if msgbuf is empty.
+			 */
+			graph_show_commit_msg(revs.graph, &buf,
+					      revs.commit_format);
+
+			/*
+			 * For CMIT_FMT_ONELINE and CMIT_FMT_USERFORMAT,
+			 * we need to add a terminating newline to the
+			 * output.
+			 *
+			 * For other formats, we want an extra padding line
+			 * after the output.
+			 */
+			if (revs.commit_format == CMIT_FMT_ONELINE ||
+			    revs.commit_format == CMIT_FMT_USERFORMAT) {
+				putchar('\n');
 			} else {
+				graph_show_padding(revs.graph);
+				putchar('\n');
+			}
+		} else {
+			if (buf.len) {
 				fwrite(buf.buf, sizeof(char), buf.len, stdout);
+				putchar('\n');
 			}
-			putchar(hdr_termination);
 		}
 		strbuf_release(&buf);
 	} else {
@@ -630,7 +629,6 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	}
 	if (revs.commit_format != CMIT_FMT_UNSPECIFIED) {
 		/* The command line has a --pretty  */
-		hdr_termination = '\n';
 		if (revs.commit_format == CMIT_FMT_ONELINE)
 			header_prefix = "";
 		else
diff --git a/graph.c b/graph.c
index 6f99063..3ecc378 100644
--- a/graph.c
+++ b/graph.c
@@ -857,3 +857,96 @@ void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)
 		p = next_p;
 	}
 }
+
+void graph_show_commit_msg(struct git_graph *graph,
+			   struct strbuf const *sb,
+			   enum cmit_fmt commit_format)
+{
+	if (!graph) {
+		/*
+		 * If there's no graph, just print the message buffer.
+		 *
+		 * The message buffer for CMIT_FMT_ONELINE and
+		 * CMIT_FMT_USERFORMAT are already missing a terminating
+		 * newline.  All of the other formats should have it.
+		 */
+		fwrite(sb->buf, sizeof(char), sb->len, stdout);
+		return;
+	}
+
+	/*
+	 * If the message buffer is empty, just print the graph output.
+	 * For example, this can happen with CMIT_FMT_USERFORMAT if the
+	 * format is the empty string.
+	 *
+	 * We need a newline first before the next graph line.
+	 */
+	if (!sb->len) {
+		if (!graph_is_commit_finished(graph)) {
+			putchar('\n');
+			graph_show_remainder(graph);
+		}
+		if (commit_format != CMIT_FMT_ONELINE &&
+		    commit_format != CMIT_FMT_USERFORMAT)
+			putchar('\n');
+		return;
+	}
+
+	/*
+	 * Show the commit message
+	 */
+	graph_show_strbuf(graph, sb);
+
+	/*
+	 * Show the remainder of the graph output,
+	 * and make sure we terminate the output properly.
+	 */
+	if (commit_format == CMIT_FMT_ONELINE ||
+	    commit_format == CMIT_FMT_USERFORMAT) {
+		/*
+		 * For CMIT_FMT_ONELINE and CMIT_FMT_USERFORMAT, we need to
+		 * make sure that the printed output still needs a
+		 * terminating newline.
+		 */
+		if (sb->buf[sb->len - 1] == '\n') {
+			/*
+			 * If the buf already ends in a newline (which can
+			 * happen with CMIT_FMT_USERFORMAT if the format
+			 * ends in "%n"), we need to print the graph output
+			 * for the start of the new line after the newline.
+			 *
+			 * Call graph_show_remainder() to let it do this.
+			 * If it doesn't print anything, call
+			 * graph_show_oneline() to force an extra line to
+			 * be printed.
+			 */
+			if (!graph_show_remainder(graph))
+				graph_show_oneline(graph);
+		} else {
+			/*
+			 * The buffer output didn't end in a newline.
+			 *
+			 * If there is more output to print, add a newline
+			 * before calling graph_show_remainder().
+			 * Otherwise, we're done.
+			 */
+			if (!graph_is_commit_finished(graph)) {
+				putchar('\n');
+				graph_show_remainder(graph);
+			}
+		}
+	} else {
+		/*
+		 * For other formats, the output we print needs to end in a
+		 * newline.  The message buffer should already end in a
+		 * newline.
+		 *
+		 * Call graph_show_remainder() to print the rest of the
+		 * graph.  If it prints anything out, we need to add a
+		 * terminating newline at the end of its output.
+		 */
+		assert(sb->buf[sb->len - 1] == '\n');
+		if (graph_show_remainder(graph))
+			putchar('\n');
+	}
+}
diff --git a/graph.h b/graph.h
index c1f6892..aa02fca 100644
--- a/graph.h
+++ b/graph.h
@@ -93,11 +93,29 @@ int graph_show_remainder(struct git_graph *graph);
  * Print a strbuf to stdout.  If the graph is non-NULL, all lines but the
  * first will be prefixed with the graph output.
  *
- * Since the firat line will not include the graph ouput, the caller is
+ * If the strbuf ends with a newline, the output will end after this
+ * newline.  A new graph line will not be printed after the final newline.
+ *
+ * Since the first line will not include the graph ouput, the caller is
  * responsible for printing this line's graph (perhaps via
  * graph_show_commit() or graph_show_oneline()) before calling
  * graph_show_strbuf().
  */
 void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
 
+/*
+ * Print a commit message strbuf and the remainder of the graph to stdout.
+ *
+ * This is similar to graph_show_strbuf(), but it always prints the
+ * remainder of the graph, and it has additional logic necessary for use by
+ * the "log" and "rev-list" commands.
+ *
+ * If cmt_format is CMIT_FMT_ONELINE or CMIT_FMT_USERFORMAT, the resulting
+ * output will still need a terminating newline.  The caller is responsible
+ * for adding this.  Otherwise, no terminating newline is needed.
+ */
+void graph_show_commit_msg(struct git_graph *graph,
+			   struct strbuf const *sb,
+			   enum cmit_fmt commit_format);
+
 #endif /* GRAPH_H */
diff --git a/log-tree.c b/log-tree.c
index 5b78d1b..0d7e521 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -247,18 +247,24 @@ void show_log(struct rev_info *opt, const char *sep)
 	}
 
 	/*
-	 * The "oneline" format has several special cases:
-	 *  - The pretty-printed commit lacks a newline at the end
-	 *    of the buffer, but we do want to make sure that we
-	 *    have a newline there. If the separator isn't already
-	 *    a newline, add an extra one.
-	 *  - unlike other log messages, the one-line format does
-	 *    not have an empty line between entries.
+	 * The "oneline" and "userformat" formats have several special
+	 * cases:
+	 *  - The pretty-printed commit needs an additional a newline at
+	 *    the end of the buffer.  (The "oneline" output never ends in a
+	 *    newline.  The "userformat" output may, but only if the user's
+	 *    format explicitly ends in "%n".)  If the separator isn't
+	 *    already a newline, add an extra one.
+	 *  - unlike other log messages, the one-line and userformat
+	 *    formats do not have an empty line between entries.
 	 */
 	extra = "";
-	if (*sep != '\n' && opt->commit_format == CMIT_FMT_ONELINE)
+	if (*sep != '\n' &&
+	    (opt->commit_format == CMIT_FMT_ONELINE ||
+	     opt->commit_format == CMIT_FMT_USERFORMAT))
 		extra = "\n";
-	if (opt->shown_one && opt->commit_format != CMIT_FMT_ONELINE) {
+	if (opt->shown_one &&
+	    (opt->commit_format != CMIT_FMT_ONELINE &&
+	     opt->commit_format != CMIT_FMT_USERFORMAT)) {
 		graph_show_padding(opt->graph);
 		putchar(opt->diffopt.line_termination);
 	}
@@ -345,34 +351,19 @@ void show_log(struct rev_info *opt, const char *sep)
 		graph_show_oneline(opt->graph);
 	}
 
-	if (msgbuf.len) {
-		if (opt->graph) {
-			graph_show_strbuf(opt->graph, &msgbuf);
-			if (opt->commit_format == CMIT_FMT_ONELINE) {
-				/*
-				 * For CMIT_FMT_ONELINE, the buffer doesn't
-				 * end in a newline, so add one first if
-				 * graph_show_remainder() needs to print
-				 * more lines.
-				 */
-				if (!graph_is_commit_finished(opt->graph)) {
-					putchar('\n');
-					graph_show_remainder(opt->graph);
-				}
-			} else {
-				/*
-				 * For other formats, we want at least one
-				 * line separating commits.  If
-				 * graph_show_remainder() doesn't print
-				 * anything, add a padding line.
-				 */
-				if (graph_show_remainder(opt->graph))
-					putchar('\n');
-			}
-		} else {
+	if (opt->graph) {
+		/*
+		 * If opt->graph is non-NULL, we always need to print
+		 * extra and sep, even if msgbuf is empty.
+		 */
+		graph_show_commit_msg(opt->graph, &msgbuf,
+				      opt->commit_format);
+		printf("%s%s", extra, sep);
+	} else {
+		if (msgbuf.len) {
 			fwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);
+			printf("%s%s", extra, sep);
 		}
-		printf("%s%s", extra, sep);
 	}
 	strbuf_release(&msgbuf);
 }
-- 
1.5.3.6

[PATCH 3/4] log and rev-list: Fix --graph output with --pretty=email

[Adam Simpkins]

As pointed out by Teemu Likonen, the initial line of
pretty_print_commit() output wasn't correctly prefixed by the graph
information.

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
 log-tree.c |    9 +++++++--
 1 files changed, 7 insertions(+), 2 deletions(-)

diff --git a/log-tree.c b/log-tree.c
index 0d7e521..d2cb26a 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -166,11 +166,16 @@ void log_write_email_headers(struct rev_info *opt, const char *name,
 	}
 
 	printf("From %s Mon Sep 17 00:00:00 2001\n", name);
-	if (opt->message_id)
+	graph_show_oneline(opt->graph);
+	if (opt->message_id) {
 		printf("Message-Id: <%s>\n", opt->message_id);
-	if (opt->ref_message_id)
+		graph_show_oneline(opt->graph);
+	}
+	if (opt->ref_message_id) {
 		printf("In-Reply-To: <%s>\nReferences: <%s>\n",
 		       opt->ref_message_id, opt->ref_message_id);
+		graph_show_oneline(opt->graph);
+	}
 	if (opt->mime_boundary) {
 		static char subject_buffer[1024];
 		static char buffer[1024];
-- 
1.5.3.6

[PATCH 4/4] log and rev-list: Improve --graph output when commits have been pruned

[Adam Simpkins]

This change automatically enables parent rewriting when --graph is
specified.  This makes the graph output look much nicer when commit
pruning is enabled.

The existing rev_info "parents" flag has been split into
two flags: "rewrite_parents" causes the parents to be rewritten, while
"print_parents" causes the log and rev-list commands to print the
parents.  The --parents option now enables both rewrite_parents and
print_parents, while --graph enables only rewrite_parents.

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
 builtin-rev-list.c |    2 +-
 log-tree.c         |    4 ++--
 revision.c         |    8 +++++---
 revision.h         |    3 ++-
 4 files changed, 10 insertions(+), 7 deletions(-)

diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index ac6a6f9..f8103bd 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -79,7 +79,7 @@ static void show_commit(struct commit *commit)
 		      stdout);
 	else
 		fputs(sha1_to_hex(commit->object.sha1), stdout);
-	if (revs.parents) {
+	if (revs.print_parents) {
 		struct commit_list *parents = commit->parents;
 		while (parents) {
 			printf(" %s", sha1_to_hex(parents->item->object.sha1));
diff --git a/log-tree.c b/log-tree.c
index d2cb26a..4ad10af 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -240,7 +240,7 @@ void show_log(struct rev_info *opt, const char *sep)
 				putchar('>');
 		}
 		fputs(diff_unique_abbrev(commit->object.sha1, abbrev_commit), stdout);
-		if (opt->parents)
+		if (opt->print_parents)
 			show_parents(commit, abbrev_commit);
 		show_decorations(commit);
 		if (opt->graph && !graph_is_commit_finished(opt->graph)) {
@@ -305,7 +305,7 @@ void show_log(struct rev_info *opt, const char *sep)
 		}
 		fputs(diff_unique_abbrev(commit->object.sha1, abbrev_commit),
 		      stdout);
-		if (opt->parents)
+		if (opt->print_parents)
 			show_parents(commit, abbrev_commit);
 		if (parent)
 			printf(" (from %s)",
diff --git a/revision.c b/revision.c
index 6a1f513..7d9d333 100644
--- a/revision.c
+++ b/revision.c
@@ -1105,7 +1105,8 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 				}
 			}
 			if (!strcmp(arg, "--parents")) {
-				revs->parents = 1;
+				revs->rewrite_parents = 1;
+				revs->print_parents = 1;
 				continue;
 			}
 			if (!strcmp(arg, "--dense")) {
@@ -1204,6 +1205,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 			}
 			if (!prefixcmp(arg, "--graph")) {
 				revs->topo_order = 1;
+				revs->rewrite_parents = 1;
 				revs->graph = graph_init();
 				continue;
 			}
@@ -1538,13 +1540,13 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)
 		/* Commit without changes? */
 		if (commit->object.flags & TREESAME) {
 			/* drop merges unless we want parenthood */
-			if (!revs->parents)
+			if (!revs->rewrite_parents)
 				return commit_ignore;
 			/* non-merge - always ignore it */
 			if (!commit->parents || !commit->parents->next)
 				return commit_ignore;
 		}
-		if (revs->parents && rewrite_parents(revs, commit) < 0)
+		if (revs->rewrite_parents && rewrite_parents(revs, commit) < 0)
 			return commit_error;
 	}
 	return commit_show;
diff --git a/revision.h b/revision.h
index d06b991..170543d 100644
--- a/revision.h
+++ b/revision.h
@@ -46,7 +46,8 @@ struct rev_info {
 			unpacked:1, /* see also ignore_packed below */
 			boundary:2,
 			left_right:1,
-			parents:1,
+			rewrite_parents:1,
+			print_parents:1,
 			reverse:1,
 			cherry_pick:1,
 			first_parent_only:1;
-- 
1.5.3.6

Re: [PATCH 1/4] Add history graph API

[Adam Simpkins]

On Mon, Apr 07, 2008 at 10:26:29AM +0300, Teemu Likonen wrote:
> 
> As I've spent some time in testing the --graph functionality I'm
> spamming my discoveries here.
> 
> When limiting the log output to a subdirectory or to a file the graph
> becomes quite hard to understand. Probably the easiest way to
> demonstrate my point is to compare side by side (for example)
> 
>   git log --graph --pretty=oneline -- Documentation/
>  
> and
> 
>   gitk -- Documentation/
> 
> in the Git repository. gitk draws lines between commits even when they
> are not in direct parent-child relationship (i.e. there is longer series
> of commits between them). With log --graph it's hard to tell which
> development line some commits come from.

Interesting, I wasn't aware of this gitk behavior.  I took a look at
the gitk code, and they're able to do this by passing the "--parents"
option to "git log".  This causes git to rewrite the parent
information so that it lists the most recent ancestor that is in the
resulting commit set, instead of the actual parent.

It was pretty easy to change "git log --graph" to do the same; I just
sent out a new patch for it.

Thanks for all the testing!

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH 2/4] log and rev-list: Fixed newline termination issues with --graph

[Junio C Hamano]

Adam Simpkins <adam@adamsimpkins.net> writes:

> The old code took care of these cases for CMIT_FMT_ONELINE, but not for
> CMIT_FMT_USERFORMAT.  For CMIT_FMT_USERFORMAT, show_log() left each
> entry without a terminating newline.  The next call to show_log() would
> then try to print an extra blank line between entries.

The log family traditionally defined LF (or NUL when -z is in effect) as
separator between each pair of entries, not as terminator after each
entry.

This was because it would make much more sense to use separator semantics
when "git log -2" and "git log -1" is asked for.  The former gives the
tip, separator (typically an extra LF), and the second, while the latter
just shows the tip.  Neither case give extra LF after the last entry.
This worked only because each entry were supposed to end with its own LF,
so separator literally "separated" each entry with an extra blank line.

ONELINE however is special cased, because it makes no sense to give an
extran blank line to separate each entry.  Compactness is the point of the
format.

Switching separator semantics to terminator semantics in USERFORMAT
unconditionally is a bit problematic, because the userformat can be used
to format multi-line entries and in that case you may want the usual
"extra blank to separate" semantics, but it often is used to define an
alternate oneline format, in which case you do want terminator semantics
instead.

I suspect that --pretty=format: (i.e. userformat) should have a way to
explicitly tell which is wanted.  Perhaps we can keep the separator
semantics not to break existing users, and introduce a dummy expand item
(say, '%_') and when it appears in the pattern it would ask for the
terminator semantics instead?

In any case, I'm happy to see that somebody started looking into this, as
this "separator vs terminator" issue in userformat has been nagging me for
quite a while.  It might be good idea to have the change independently
from the graph extension first and then build the graph stuff on top of
the solidified base.  I dunno...

Re: [PATCH 1/4] Add history graph API

[Adam Simpkins]

On Mon, Apr 07, 2008 at 08:24:10AM +0300, Teemu Likonen wrote:
> Adam Simpkins kirjoitti:
> 
> > Actually, going back and testing this, it looks like I have a bug
> > when handling --graph together with --pretty=format.  There's a
> > missing newline after the user's format message and the next graph
> > line.  I'll try to fix this and submit a patch later this evening.
> 
> Also, the output is not indented for options that display some 
> additional information to commit message. Those include:
> 
> --raw
> --stat
> --numstat
> --shortstat
> --summary
> --name-only
> --name-status
> 
> I'm not sure if the diff output of -p, -u etc. should be 
> indented--probably not--but for different stat and summary options it 
> would be nice to not have their output displayed over the graph area. 
> Especially --name-status is funny since it displays "M" to column 1 to 
> indicate modified file while "M" also means merge commit in the graph.

Hmm.  This is a harder problem to fix.  All of the options you list
above are handled by the internal diff API.  The diff API doesn't have
any knowledge about log and rev-list options, such as --graph.

The nicest way to fix this would probably be to write new diff API
functions that output to a strbuf instead of printing directly to
stdout.  Then the log code could prefix each line of the buffer with
the graph info before printing it.

However, this would be a lot of work, and I'm not sure that it's
really worth the effort at the moment.  For now, I'm leaning towards
changing the code to just exit with an error if --graph is used with
any of these options.

Any opinions?  Alternative suggestions?

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH 2/4] log and rev-list: Fixed newline termination issues with --graph

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> I suspect that --pretty=format: (i.e. userformat) should have a way to
> explicitly tell which is wanted.  Perhaps we can keep the separator
> semantics not to break existing users, and introduce a dummy expand item
> (say, '%_') and when it appears in the pattern it would ask for the
> terminator semantics instead?
>
> In any case, I'm happy to see that somebody started looking into this, as
> this "separator vs terminator" issue in userformat has been nagging me for
> quite a while.  It might be good idea to have the change independently
> from the graph extension first and then build the graph stuff on top of
> the solidified base.  I dunno...

Some alternatives to specify terminator semantics I considered are:

 (1) Presence of %_ in "--pretty=format:..." triggers terminator
     semantics and %_ itself interpolates an empty string; otherwise
     separator semantics is used.

 (2) Presence of %n in "--pretty=format:..." means a multi-line output and
     uses separator as before; lack of %n means it is a one-line format
     and uses terminator.

 (3) A new option --pretty=tformat:... (i.e. tformat instead of format)
     means LF (or NUL) is used as terminator instead of separator;

 (4) A new syntax --pretty=format/... (i.e. slash instead of the usual
     colon) means LF (or NUL) is used as terminator instead of separator;

The first one is what I suggested in the message, but it feels somewhat
hacky.  I suspect that the second one would catch 99% of the cases, but it
is DWIM and it is known that DWIM can go wrong.  I favor design along
the lines of (3) or (4), which I think would be much cleaner.

I however do not particularly like either "tformat" which is a non-word,
nor ":" vs "/" whose differences do not intuitively translate to
"separator vs terminator" distinction.

Re: [PATCH 1/4] Add history graph API

[Teemu Likonen]

Adam Simpkins kirjoitti (7.4.2008 klo 1.34):

> The nicest way to fix this would probably be to write new diff API
> functions that output to a strbuf instead of printing directly to
> stdout.  Then the log code could prefix each line of the buffer with
> the graph info before printing it.
> 
> However, this would be a lot of work, and I'm not sure that it's
> really worth the effort at the moment.  For now, I'm leaning towards
> changing the code to just exit with an error if --graph is used with
> any of these options.
> 
> Any opinions?  Alternative suggestions?

Ok, then I'd suggest that it's left as is. The --graph may be useful
with some stat options even when the graph area is parially broken by
some other output.

[PATCH v2] bash: Add more command line option completions for 'git log'

[Teemu Likonen]

Signed-off-by: Teemu Likonen <tlikonen@iki.fi>
---

Hmm, why not add some more useful long options? There are plenty of them of
course but I feel these are one of the most common.


 contrib/completion/git-completion.bash |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 4d81963..02a5fd3 100755
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -757,6 +757,8 @@ _git_log ()
 			--pretty= --name-status --name-only --raw
 			--not --all
 			--left-right --cherry-pick
+			--graph --stat --numstat --shortstat
+			--decorate --diff-filter=
 			"
 		return
 		;;
-- 
1.5.5.rc3.24.g129ac

Re: [PATCH 2/4] log and rev-list: Fixed newline termination issues with --graph

[Jeff King]

On Mon, Apr 07, 2008 at 01:52:40AM -0700, Junio C Hamano wrote:

> Some alternatives to specify terminator semantics I considered are:
> [...]
> The first one is what I suggested in the message, but it feels somewhat
> hacky.  I suspect that the second one would catch 99% of the cases, but it
> is DWIM and it is known that DWIM can go wrong.  I favor design along
> the lines of (3) or (4), which I think would be much cleaner.

How about:

  (5) There is no automagic terminator or separator for user formats. %n
      translates to a newline. %N translates to a newline, unless this
      is the final record, in which case it translates to the empty
      string.

So:
    # oneline
    git log --pretty=format:'%h %s%n'
    # multiline
    git log --pretty=format:'%h%nSubject: %s%n%N'

The main drawback is that dropping the automatic separator breaks
existing uses. We could work around this by automatically appending '%n'
if there is no use of "%n" or "%N", but I think that DWIM won't work for
formats which want a non-newline record separator. So maybe a %x/%X
string to mean "separator / terminator" instead of building on newline.
If one doesn't exist, we append "%x" to the format (to give oneline
semantics).

-Peff

Re: [PATCH 2/4] log and rev-list: Fixed newline termination issues with --graph

[Jakub Narebski]

Junio C Hamano <gitster@pobox.com> writes:
> Junio C Hamano <gitster@pobox.com> writes:
> 
> > I suspect that --pretty=format: (i.e. userformat) should have a way to
> > explicitly tell which is wanted.  Perhaps we can keep the separator
> > semantics not to break existing users, and introduce a dummy expand item
> > (say, '%_') and when it appears in the pattern it would ask for the
> > terminator semantics instead?
> >
> > In any case, I'm happy to see that somebody started looking into this, as
> > this "separator vs terminator" issue in userformat has been nagging me for
> > quite a while.  It might be good idea to have the change independently
> > from the graph extension first and then build the graph stuff on top of
> > the solidified base.  I dunno...
> 
> Some alternatives to specify terminator semantics I considered are:
> 
>  (1) Presence of %_ in "--pretty=format:..." triggers terminator
>      semantics and %_ itself interpolates an empty string; otherwise
>      separator semantics is used.

Or %_ might interpolate to _single_ separator, swallowing all
separators that follows it (something like collapsing whitespace).
Either that, or %_ interpolate to separator value, and %*_ collapses
separators (terminators).
 
Bit less hacky, bit more geeky.

>  (2) Presence of %n in "--pretty=format:..." means a multi-line output and
>      uses separator as before; lack of %n means it is a one-line format
>      and uses terminator.

I guess that literal newline in format would also mean multi-line
output.  Also '%b' (body) should mean multi-line output.


BTW. rpm uses [% ... ] to iterate over a set of (parallel) arrays
in --queryformat, which is a bit similar to --pretty=format:<fmt>,
e.g. 'rpm -q --queryformat "[%-50{FILENAMES} %10{FILESIZES}\n]'

BTW2. git-for-each-ref uses _different_ kind of format, %(<name>) and
not %<char>.

>  (3) A new option --pretty=tformat:... (i.e. tformat instead of format)
>      means LF (or NUL) is used as terminator instead of separator;
> 
>  (4) A new syntax --pretty=format/... (i.e. slash instead of the usual
>      colon) means LF (or NUL) is used as terminator instead of separator;
> 
> The first one is what I suggested in the message, but it feels somewhat
> hacky.  I suspect that the second one would catch 99% of the cases, but it
> is DWIM and it is known that DWIM can go wrong.  I favor design along
> the lines of (3) or (4), which I think would be much cleaner.
> 
> I however do not particularly like either "tformat" which is a non-word,
> nor ":" vs "/" whose differences do not intuitively translate to
> "separator vs terminator" distinction.

"|" instead of ":" wouldn't be a good idea?

-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: [PATCH 1/4] Add history graph API

[Linus Torvalds]

On Sun, 6 Apr 2008, Johannes Schindelin wrote:
> 
> AFAICT you do not even need them then.  Using "struct strbuf *" without 
> ever declaring struct strbuf before that is perfectly valid.

In traditional C, and inside structure declarations etc, yes.

In modern C, in other contexts, no.

Modern C considers a function declaration to be its own scope (it's the 
scope of the function definition, which in a declaration is obviously 
just the declaration). So if you use a "struct xyzzy *" in a function 
declaration, it will be a *different* "struct xyzzy *" from one declared 
later.

Try to compile something like this:

	int fn(struct xyzzy *);
	int fn(struct xyzzy *);

with a modern C compiler, and it will actually say something along the 
lines of "conflicting types for ‘fn’", because while the two declarations 
look identical, they actually have two different (private) declarations of 
"struct xyzzy" going on.

But to make it even more interesting, you don't actually need a full 
declaration of "struct xyzzy" to make the compiler happy, you only need an 
implicit one ahead of time. You can do that with the incomplete 
declaration, of course (like the --graph patch did), ie just a simple

	struct xyzzy;

before those declarations is sufficient, but so is the implicit 
declaration of just using the pointer to it in some non-private scope, ie 
it's equally valid to do

	struct foobar {
		struct xyzzy *ptr;
	};

and this will already be enough to declare "struct xyzzy" in scope for the 
function declarations afterwards.

Is this illogical? Somewhat. Why is it a private scope in a function 
declaration but not in a struct declaration? Why isn't the function scope 
limited to the stuff *inside* the function? Somebody probably knows, but 
for the rest of us the answer is just "that's how it is, deal with it".

			Linus

Re: [PATCH 2/4] log and rev-list: Fixed newline termination issues with --graph

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> The main drawback is that dropping the automatic separator breaks
> existing uses. We could work around this by automatically appending '%n'
> if there is no use of "%n" or "%N",...

Yeah, I agree that sounds quite bad, and that is why I favor more explicit
and independent way to choose between separator and terminator (like the
"tformat" thing).

Re: [PATCH 2/4] log and rev-list: Fixed newline termination issues with --graph

[Adam Simpkins]

On Mon, Apr 07, 2008 at 10:43:09AM -0700, Junio C Hamano wrote:
> Jeff King <peff@peff.net> writes:
> 
> > The main drawback is that dropping the automatic separator breaks
> > existing uses. We could work around this by automatically appending '%n'
> > if there is no use of "%n" or "%N",...
> 
> Yeah, I agree that sounds quite bad, and that is why I favor more explicit
> and independent way to choose between separator and terminator (like the
> "tformat" thing).

How about an extra option to explicitly toggle the separator on or
off?  For example, how about "--sep=<count>"?  Using --sep=0 would put
no separator between entries.  --sep=N would put N separators between
entries.

If this option isn't explicitly specified, the default should be
--sep=0 for ONELINE, and --sep=1 for everything else.  Using --sep=2
with USERFORMAT would achieve the behavior of getting an extra line of
padding between entries.


This still leaves unresolved the fact that the USERFORMAT output ends
with a missing newline in most cases.  I can see the argument for
doing this when using -z, which is primarily aimed for programmatic
consumption.  However, without -z, I don't think this is the behavior
most users expect.  For example, try running
"git --no-pager log -1 --pretty=format:%H".

If we were starting from scratch, and didn't have to worry about
breaking existing behavior, I would say that USERFORMAT should always
terminate entries in a newline, and then default to --sep=0.  As it
is, it might be easiest just to leave the current behavior, without a
terminating newline.

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH 2/4] log and rev-list: Fixed newline termination issues with --graph

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

>  (2) Presence of %n in "--pretty=format:..." means a multi-line output and
>      uses separator as before; lack of %n means it is a one-line format
>      and uses terminator.

After thinking about this a bit more, I think a slight variant of the
above probably is the least intrusive both from code and semantics point
of view, and would match end-user expectations pretty well.

This attached patch introduces a single bit "use_terminator" in "struct
rev_info", which is normally false (i.e. most formats use separator
semantics) but by flipping it to true, you can ask for terminator
semantics just like oneline format does.

The function get_commit_format(), which is what parses "--pretty=" option,
now takes a pointer to "struct rev_info" and updates its commit_format and
use_terminator fields.  It used to return the value of type "enum
cmit_fmt", but all the callers assigned it to rev->commit_format.

There are only two cases the code turns use_terminator on.  Obviously, the
traditional oneline format (--pretty=oneline) is one of them, and the new
case is --pretty=format:... that does not end with "%n".

When the custom format "--pretty=format:" is:

	"A: %an <%ae>%nC: %cn <%ce>%n"

it represents a record with two lines (author and committer), and these
are output with an extra LF in between, just like the regular --pretty
without customization will get an extra separator.  The custom format

	"A: %an <%ae> C: %cn <%ce>"

will give a one-line-per-commit output, each of which is terminated with
LF.  And

	"A: %an <%ae>%nC: %cn <%ce>"

will give two line per commit without extra separator.

---

 builtin-commit.c |    2 +-
 builtin-log.c    |    3 ++-
 commit.h         |    3 ++-
 log-tree.c       |    4 ++--
 pretty.c         |   25 ++++++++++++++++++-------
 revision.c       |    2 +-
 revision.h       |    3 ++-
 7 files changed, 28 insertions(+), 14 deletions(-)

diff --git a/builtin-commit.c b/builtin-commit.c
index 660a345..8bf3503 100644
--- a/builtin-commit.c
+++ b/builtin-commit.c
@@ -810,7 +810,7 @@ static void print_summary(const char *prefix, const unsigned char *sha1)
 
 	rev.verbose_header = 1;
 	rev.show_root_diff = 1;
-	rev.commit_format = get_commit_format("format:%h: %s");
+	get_commit_format("format:%h: %s", &rev);
 	rev.always_show_header = 0;
 	rev.diffopt.detect_rename = 1;
 	rev.diffopt.rename_limit = 100;
diff --git a/builtin-log.c b/builtin-log.c
index 5c00725..1670d0b 100644
--- a/builtin-log.c
+++ b/builtin-log.c
@@ -56,7 +56,7 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,
 	rev->abbrev = DEFAULT_ABBREV;
 	rev->commit_format = CMIT_FMT_DEFAULT;
 	if (fmt_pretty)
-		rev->commit_format = get_commit_format(fmt_pretty);
+		get_commit_format(fmt_pretty, rev);
 	rev->verbose_header = 1;
 	DIFF_OPT_SET(&rev->diffopt, RECURSIVE);
 	rev->show_root_diff = default_show_root;
@@ -400,6 +400,7 @@ int cmd_log_reflog(int argc, const char **argv, const char *prefix)
 	 * allow us to set a different default.
 	 */
 	rev.commit_format = CMIT_FMT_ONELINE;
+	rev.use_terminator = 1;
 	rev.always_show_header = 1;
 
 	/*
diff --git a/commit.h b/commit.h
index 2f63bc8..2d94d41 100644
--- a/commit.h
+++ b/commit.h
@@ -63,7 +63,8 @@ enum cmit_fmt {
 };
 
 extern int non_ascii(int);
-extern enum cmit_fmt get_commit_format(const char *arg);
+struct rev_info; /* in revision.h, it circularly uses enum cmit_fmt */
+extern void get_commit_format(const char *arg, struct rev_info *);
 extern void format_commit_message(const struct commit *commit,
                                   const void *format, struct strbuf *sb);
 extern void pretty_print_commit(enum cmit_fmt fmt, const struct commit*,
diff --git a/log-tree.c b/log-tree.c
index 5b29639..d246147 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -249,9 +249,9 @@ void show_log(struct rev_info *opt, const char *sep)
 	 *    not have an empty line between entries.
 	 */
 	extra = "";
-	if (*sep != '\n' && opt->commit_format == CMIT_FMT_ONELINE)
+	if (*sep != '\n' && opt->use_terminator)
 		extra = "\n";
-	if (opt->shown_one && opt->commit_format != CMIT_FMT_ONELINE)
+	if (opt->shown_one && !opt->use_terminator)
 		putchar(opt->diffopt.line_termination);
 	opt->shown_one = 1;
 
diff --git a/pretty.c b/pretty.c
index 16bfb86..365e387 100644
--- a/pretty.c
+++ b/pretty.c
@@ -21,23 +21,34 @@ static struct cmt_fmt_map {
 
 static char *user_format;
 
-enum cmit_fmt get_commit_format(const char *arg)
+void get_commit_format(const char *arg, struct rev_info *rev)
 {
 	int i;
 
-	if (!arg || !*arg)
-		return CMIT_FMT_DEFAULT;
+	rev->use_terminator = 0;
+	if (!arg || !*arg) {
+		rev->commit_format = CMIT_FMT_DEFAULT;
+		return;
+	}
 	if (*arg == '=')
 		arg++;
 	if (!prefixcmp(arg, "format:")) {
+		size_t len = strlen(arg + 7);
 		free(user_format);
 		user_format = xstrdup(arg + 7);
-		return CMIT_FMT_USERFORMAT;
+		if (len < 2 || strcmp(user_format + len - 2, "%n"))
+			rev->use_terminator = 1;
+		rev->commit_format = CMIT_FMT_USERFORMAT;
+		return;
 	}
-	for (i = 0; i < ARRAY_SIZE(cmt_fmts); i++) {
+	for (i = 0; i < ARRAY_SIZE(cmt_fmts) - 1; i++) {
 		if (!strncmp(arg, cmt_fmts[i].n, cmt_fmts[i].cmp_len) &&
-		    !strncmp(arg, cmt_fmts[i].n, strlen(arg)))
-			return cmt_fmts[i].v;
+		    !strncmp(arg, cmt_fmts[i].n, strlen(arg))) {
+			if (cmt_fmts[i].v == CMIT_FMT_ONELINE)
+				rev->use_terminator = 0;
+			rev->commit_format = cmt_fmts[i].v;
+			return;
+		}
 	}
 
 	die("invalid --pretty format: %s", arg);
diff --git a/revision.c b/revision.c
index 196fedc..781c503 100644
--- a/revision.c
+++ b/revision.c
@@ -1198,7 +1198,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 			}
 			if (!prefixcmp(arg, "--pretty")) {
 				revs->verbose_header = 1;
-				revs->commit_format = get_commit_format(arg+8);
+				get_commit_format(arg+8, revs);
 				continue;
 			}
 			if (!strcmp(arg, "--root")) {
diff --git a/revision.h b/revision.h
index c8b3b94..31217f8 100644
--- a/revision.h
+++ b/revision.h
@@ -64,7 +64,8 @@ struct rev_info {
 
 	/* Format info */
 	unsigned int	shown_one:1,
-			abbrev_commit:1;
+			abbrev_commit:1,
+			use_terminator:1;
 	enum date_mode date_mode;
 
 	const char **ignore_packed; /* pretend objects in these are unpacked */

Re: [PATCH 2/4] log and rev-list: Fixed newline termination issues with --graph

[Govind Salinas]

On Mon, Apr 7, 2008 at 7:11 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Junio C Hamano <gitster@pobox.com> writes:
>
>  >  (2) Presence of %n in "--pretty=format:..." means a multi-line output and
>  >      uses separator as before; lack of %n means it is a one-line format
>  >      and uses terminator.
>
>  After thinking about this a bit more, I think a slight variant of the
>  above probably is the least intrusive both from code and semantics point
>  of view, and would match end-user expectations pretty well.
>
>  This attached patch introduces a single bit "use_terminator" in "struct
>  rev_info", which is normally false (i.e. most formats use separator
>  semantics) but by flipping it to true, you can ask for terminator
>  semantics just like oneline format does.
>
>  The function get_commit_format(), which is what parses "--pretty=" option,
>  now takes a pointer to "struct rev_info" and updates its commit_format and
>  use_terminator fields.  It used to return the value of type "enum
>  cmit_fmt", but all the callers assigned it to rev->commit_format.
>
>  There are only two cases the code turns use_terminator on.  Obviously, the
>  traditional oneline format (--pretty=oneline) is one of them, and the new
>  case is --pretty=format:... that does not end with "%n".
>
>  When the custom format "--pretty=format:" is:
>
>         "A: %an <%ae>%nC: %cn <%ce>%n"
>
>  it represents a record with two lines (author and committer), and these
>  are output with an extra LF in between, just like the regular --pretty
>  without customization will get an extra separator.  The custom format
>
>         "A: %an <%ae> C: %cn <%ce>"
>
>  will give a one-line-per-commit output, each of which is terminated with
>  LF.  And
>
>         "A: %an <%ae>%nC: %cn <%ce>"
>
>  will give two line per commit without extra separator.
>

Hi,

Shouldn't whatever option is used here respect line_terminator such
that it will use NULL bytes when -z is used?  Having watched this
discussion, it seems like you really want an option --whatever that
forces a record terminator between records and, I assume, at the end.
I have not seen anyone suggest it, perhaps I missed it.

-Govind

Re: [PATCH 2/4] log and rev-list: Fixed newline termination issues with --graph

[Junio C Hamano]

"Govind Salinas" <blix@sophiasuchtig.com> writes:

> Shouldn't whatever option is used here respect line_terminator such
> that it will use NULL bytes when -z is used?

Yes but it is orthogonal to what is being discussed.  What the patch shows
is how to allow --pretty=format: to conditionally do what --pretty=oneline
already does.  If the current --pretty=oneline forces "\n" under -z (I
haven't checked if that is the case) that might be something we may want
to change.  Once you do so, you would get the same fix for --pretty=format
for free ;-)

Also when you talk about line_terminator, you need to be careful to
realize that it is _not_ really a "line_terminator".  For example, we do
not substitute 's/\n/\0/' the EOLN in multi-line log messages.  Neither do
we use NUL terminated lines in diff nor stat output when -p and --stat are
in effect.  They are more like "separator between parts of output".