Merge branch 'as/graph'

* as/graph:
  get_revision(): honor the topo_order flag for boundary commits
  Fix output of "git log --graph --boundary"
  log --graph --left-right: show left/right information in place of '*'
  graph API: don't print branch lines for uninteresting merge parents
  graph API: fix graph mis-alignment after uninteresting commits

6 files changed, 191 insertions, 62 deletions

diff --git a/Documentation/technical/api-history-graph.txt b/Documentation/technical/api-history-graph.txt
index ce1c08ee86..e9559790a3 100644
--- a/Documentation/technical/api-history-graph.txt
+++ b/Documentation/technical/api-history-graph.txt
@@ -115,7 +115,7 @@ Sample usage
 
 ------------
 struct commit *commit;
-struct git_graph *graph = graph_init();
+struct git_graph *graph = graph_init(opts);
 
 while ((commit = get_revision(opts)) != NULL) {
 	graph_update(graph, commit);
diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index 54d55cc3a3..b474527402 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -65,15 +65,18 @@ static void show_commit(struct commit *commit)
 		printf("%lu ", commit->date);
 	if (header_prefix)
 		fputs(header_prefix, stdout);
-	if (commit->object.flags & BOUNDARY)
-		putchar('-');
-	else if (commit->object.flags & UNINTERESTING)
-		putchar('^');
-	else if (revs.left_right) {
-		if (commit->object.flags & SYMMETRIC_LEFT)
-			putchar('<');
-		else
-			putchar('>');
+
+	if (!revs.graph) {
+		if (commit->object.flags & BOUNDARY)
+			putchar('-');
+		else if (commit->object.flags & UNINTERESTING)
+			putchar('^');
+		else if (revs.left_right) {
+			if (commit->object.flags & SYMMETRIC_LEFT)
+				putchar('<');
+			else
+				putchar('>');
+		}
 	}
 	if (revs.abbrev_commit && revs.abbrev)
 		fputs(find_unique_abbrev(commit->object.sha1, revs.abbrev),
diff --git a/graph.c b/graph.c
index 9d6ed30b0b..26b8c5209e 100644
--- a/graph.c
+++ b/graph.c
@@ -54,10 +54,14 @@ struct git_graph {
 	 * The commit currently being processed
 	 */
 	struct commit *commit;
+	/* The rev-info used for the current traversal */
+	struct rev_info *revs;
 	/*
-	 * The number of parents this commit has.
-	 * (Stored so we don't have to walk over them each time we need
-	 * this number)
+	 * The number of interesting parents that this commit has.
+	 *
+	 * Note that this is not the same as the actual number of parents.
+	 * This count excludes parents that won't be printed in the graph
+	 * output, as determined by graph_is_interesting().
 	 */
 	int num_parents;
 	/*
@@ -125,10 +129,11 @@ struct git_graph {
 	int *new_mapping;
 };
 
-struct git_graph *graph_init(void)
+struct git_graph *graph_init(struct rev_info *opt)
 {
 	struct git_graph *graph = xmalloc(sizeof(struct git_graph));
 	graph->commit = NULL;
+	graph->revs = opt;
 	graph->num_parents = 0;
 	graph->expansion_row = 0;
 	graph->state = GRAPH_PADDING;
@@ -180,6 +185,28 @@ static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
 				      sizeof(int) * 2 * graph->column_capacity);
 }
 
+/*
+ * Returns 1 if the commit will be printed in the graph output,
+ * and 0 otherwise.
+ */
+static int graph_is_interesting(struct git_graph *graph, struct commit *commit)
+{
+	/*
+	 * If revs->boundary is set, commits whose children have
+	 * been shown are always interesting, even if they have the
+	 * UNINTERESTING or TREESAME flags set.
+	 */
+	if (graph->revs && graph->revs->boundary) {
+		if (commit->object.flags & CHILD_SHOWN)
+			return 1;
+	}
+
+	/*
+	 * Uninteresting and pruned commits won't be printed
+	 */
+	return (commit->object.flags & (UNINTERESTING | TREESAME)) ? 0 : 1;
+}
+
 static void graph_insert_into_new_columns(struct git_graph *graph,
 					  struct commit *commit,
 					  int *mapping_index)
@@ -187,9 +214,9 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 	int i;
 
 	/*
-	 * Ignore uinteresting and pruned commits
+	 * Ignore uinteresting commits
 	 */
-	if (commit->object.flags & (UNINTERESTING | TREESAME))
+	if (!graph_is_interesting(graph, commit))
 		return;
 
 	/*
@@ -228,8 +255,8 @@ static void graph_update_width(struct git_graph *graph,
 	int max_cols = graph->num_columns + graph->num_parents;
 
 	/*
-	 * Even if the current commit has no parents, it still takes up a
-	 * column for itself.
+	 * Even if the current commit has no parents to be printed, it
+	 * still takes up a column for itself.
 	 */
 	if (graph->num_parents < 1)
 		max_cols++;
@@ -313,6 +340,7 @@ static void graph_update_columns(struct git_graph *graph)
 		}
 
 		if (col_commit == graph->commit) {
+			int old_mapping_idx = mapping_idx;
 			seen_this = 1;
 			for (parent = graph->commit->parents;
 			     parent;
@@ -321,6 +349,14 @@ static void graph_update_columns(struct git_graph *graph)
 							      parent->item,
 							      &mapping_idx);
 			}
+			/*
+			 * We always need to increment mapping_idx by at
+			 * least 2, even if it has no interesting parents.
+			 * The current commit always takes up at least 2
+			 * spaces.
+			 */
+			if (mapping_idx == old_mapping_idx)
+				mapping_idx += 2;
 		} else {
 			graph_insert_into_new_columns(graph, col_commit,
 						      &mapping_idx);
@@ -350,11 +386,13 @@ void graph_update(struct git_graph *graph, struct commit *commit)
 	graph->commit = commit;
 
 	/*
-	 * Count how many parents this commit has
+	 * Count how many interesting parents this commit has
 	 */
 	graph->num_parents = 0;
-	for (parent = commit->parents; parent; parent = parent->next)
-		graph->num_parents++;
+	for (parent = commit->parents; parent; parent = parent->next) {
+		if (graph_is_interesting(graph, parent->item))
+			graph->num_parents++;
+	}
 
 	/*
 	 * Call graph_update_columns() to update
@@ -515,6 +553,51 @@ static void graph_output_pre_commit_line(struct git_graph *graph,
 		graph->state = GRAPH_COMMIT;
 }
 
+static void graph_output_commit_char(struct git_graph *graph, struct strbuf *sb)
+{
+	/*
+	 * For boundary commits, print 'o'
+	 * (We should only see boundary commits when revs->boundary is set.)
+	 */
+	if (graph->commit->object.flags & BOUNDARY) {
+		assert(graph->revs->boundary);
+		strbuf_addch(sb, 'o');
+		return;
+	}
+
+	/*
+	 * If revs->left_right is set, print '<' for commits that
+	 * come from the left side, and '>' for commits from the right
+	 * side.
+	 */
+	if (graph->revs && graph->revs->left_right) {
+		if (graph->commit->object.flags & SYMMETRIC_LEFT)
+			strbuf_addch(sb, '<');
+		else
+			strbuf_addch(sb, '>');
+		return;
+	}
+
+	/*
+	 * Print 'M' for merge commits
+	 *
+	 * Note that we don't check graph->num_parents to determine if the
+	 * commit is a merge, since that only tracks the number of
+	 * "interesting" parents.  We want to print 'M' for merge commits
+	 * even if they have less than 2 interesting parents.
+	 */
+	if (graph->commit->parents != NULL &&
+	    graph->commit->parents->next != NULL) {
+		strbuf_addch(sb, 'M');
+		return;
+	}
+
+	/*
+	 * Print '*' in all other cases
+	 */
+	strbuf_addch(sb, '*');
+}
+
 void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 {
 	int seen_this = 0;
@@ -540,10 +623,7 @@ void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 
 		if (col_commit == graph->commit) {
 			seen_this = 1;
-			if (graph->num_parents > 1)
-				strbuf_addch(sb, 'M');
-			else
-				strbuf_addch(sb, '*');
+			graph_output_commit_char(graph, sb);
 
 			if (graph->num_parents < 2)
 				strbuf_addch(sb, ' ');
diff --git a/graph.h b/graph.h
index a7748a5b22..eab4e3daba 100644
--- a/graph.h
+++ b/graph.h
@@ -8,7 +8,7 @@ struct git_graph;
  * Create a new struct git_graph.
  * The graph should be freed with graph_release() when no longer needed.
  */
-struct git_graph *graph_init();
+struct git_graph *graph_init(struct rev_info *opt);
 
 /*
  * Destroy a struct git_graph and free associated memory.
diff --git a/log-tree.c b/log-tree.c
index 1474d1f5d9..5505606ed6 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -228,15 +228,17 @@ void show_log(struct rev_info *opt)
 	if (!opt->verbose_header) {
 		graph_show_commit(opt->graph);
 
-		if (commit->object.flags & BOUNDARY)
-			putchar('-');
-		else if (commit->object.flags & UNINTERESTING)
-			putchar('^');
-		else if (opt->left_right) {
-			if (commit->object.flags & SYMMETRIC_LEFT)
-				putchar('<');
-			else
-				putchar('>');
+		if (!opt->graph) {
+			if (commit->object.flags & BOUNDARY)
+				putchar('-');
+			else if (commit->object.flags & UNINTERESTING)
+				putchar('^');
+			else if (opt->left_right) {
+				if (commit->object.flags & SYMMETRIC_LEFT)
+					putchar('<');
+				else
+					putchar('>');
+			}
 		}
 		fputs(diff_unique_abbrev(commit->object.sha1, abbrev_commit), stdout);
 		if (opt->print_parents)
@@ -293,15 +295,18 @@ void show_log(struct rev_info *opt)
 		fputs(diff_get_color_opt(&opt->diffopt, DIFF_COMMIT), stdout);
 		if (opt->commit_format != CMIT_FMT_ONELINE)
 			fputs("commit ", stdout);
-		if (commit->object.flags & BOUNDARY)
-			putchar('-');
-		else if (commit->object.flags & UNINTERESTING)
-			putchar('^');
-		else if (opt->left_right) {
-			if (commit->object.flags & SYMMETRIC_LEFT)
-				putchar('<');
-			else
-				putchar('>');
+
+		if (!opt->graph) {
+			if (commit->object.flags & BOUNDARY)
+				putchar('-');
+			else if (commit->object.flags & UNINTERESTING)
+				putchar('^');
+			else if (opt->left_right) {
+				if (commit->object.flags & SYMMETRIC_LEFT)
+					putchar('<');
+				else
+					putchar('>');
+			}
 		}
 		fputs(diff_unique_abbrev(commit->object.sha1, abbrev_commit),
 		      stdout);
diff --git a/revision.c b/revision.c
index 7142cf96cd..fb9924e5af 100644
--- a/revision.c
+++ b/revision.c
@@ -1205,7 +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();
+				revs->graph = graph_init(revs);
 				continue;
 			}
 			if (!strcmp(arg, "--root")) {
@@ -1612,28 +1612,62 @@ static void gc_boundary(struct object_array *array)
 	}
 }
 
+static void create_boundary_commit_list(struct rev_info *revs)
+{
+	unsigned i;
+	struct commit *c;
+	struct object_array *array = &revs->boundary_commits;
+	struct object_array_entry *objects = array->objects;
+
+	/*
+	 * If revs->commits is non-NULL at this point, an error occurred in
+	 * get_revision_1().  Ignore the error and continue printing the
+	 * boundary commits anyway.  (This is what the code has always
+	 * done.)
+	 */
+	if (revs->commits) {
+		free_commit_list(revs->commits);
+		revs->commits = NULL;
+	}
+
+	/*
+	 * Put all of the actual boundary commits from revs->boundary_commits
+	 * into revs->commits
+	 */
+	for (i = 0; i < array->nr; i++) {
+		c = (struct commit *)(objects[i].item);
+		if (!c)
+			continue;
+		if (!(c->object.flags & CHILD_SHOWN))
+			continue;
+		if (c->object.flags & (SHOWN | BOUNDARY))
+			continue;
+		c->object.flags |= BOUNDARY;
+		commit_list_insert(c, &revs->commits);
+	}
+
+	/*
+	 * If revs->topo_order is set, sort the boundary commits
+	 * in topological order
+	 */
+	sort_in_topological_order(&revs->commits, revs->lifo);
+}
+
 static struct commit *get_revision_internal(struct rev_info *revs)
 {
 	struct commit *c = NULL;
 	struct commit_list *l;
 
 	if (revs->boundary == 2) {
-		unsigned i;
-		struct object_array *array = &revs->boundary_commits;
-		struct object_array_entry *objects = array->objects;
-		for (i = 0; i < array->nr; i++) {
-			c = (struct commit *)(objects[i].item);
-			if (!c)
-				continue;
-			if (!(c->object.flags & CHILD_SHOWN))
-				continue;
-			if (!(c->object.flags & SHOWN))
-				break;
-		}
-		if (array->nr <= i)
-			return NULL;
-
-		c->object.flags |= SHOWN | BOUNDARY;
+		/*
+		 * All of the normal commits have already been returned,
+		 * and we are now returning boundary commits.
+		 * create_boundary_commit_list() has populated
+		 * revs->commits with the remaining commits to return.
+		 */
+		c = pop_commit(&revs->commits);
+		if (c)
+			c->object.flags |= SHOWN;
 		return c;
 	}
 
@@ -1697,7 +1731,14 @@ static struct commit *get_revision_internal(struct rev_info *revs)
 		 * switch to boundary commits output mode.
 		 */
 		revs->boundary = 2;
-		return get_revision(revs);
+
+		/*
+		 * Update revs->commits to contain the list of
+		 * boundary commits.
+		 */
+		create_boundary_commit_list(revs);
+
+		return get_revision_internal(revs);
 	}
 
 	/*