[PATCH 0/2] Fix output of "git log --graph --boundary"

[PATCH 0/2] Fix output of "git log --graph --boundary"

[Adam Simpkins]

These two patches fix the graph output when --boundary is used.  They
apply on top of a merge of my recent fixes for handling uninteresting
commits (since they use the new graph_is_interesting() function I
added), and Dscho's "--graph --left-right" changes (since these changes
also need the struct rev_info).

There were two small conflicts when merging Dscho's and my changes.
I've including a merge diff below showing how I resolved them.


Adam Simpkins (2):
  Fix output of "git log --graph --boundary"
  get_revision(): honor the topo_order flag for boundary commits

 graph.c    |   87 ++++++++++++++++++++++++++++++++++++++++-------------------
 revision.c |   75 ++++++++++++++++++++++++++++++++++++++++-----------
 2 files changed, 117 insertions(+), 45 deletions(-)


8acd45e94a0d42a0ceb164e294049104e0c0f663
diff --cc graph.c
index ba9ede0,85a9ba0..479035d
--- a/graph.c
+++ b/graph.c
@@@ -55,11 -55,13 +55,15 @@@ struct git_graph 
  	 */
  	struct commit *commit;
  	/*
+ 	 * For the --left-right option.
+ 	 */
+ 	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;
  	/*
@@@ -565,18 -545,14 +570,28 @@@ void graph_output_commit_line(struct gi
  
  		if (col_commit == graph->commit) {
  			seen_this = 1;
 +			/*
- 			 * If the commit is a merge, print 'M'.  Otherwise,
- 			 * print '*'.
++			 * If revs->left_right is set, print the '<' or '>'
++			 * depending on which side this commit came from.
++			 *
++			 * If revs->left_right is not set and the commit is
++			 * a merge, print 'M'.  Otherwise, print '*'.
 +			 *
 +			 * 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)
+ 			if (graph->revs && graph->revs->left_right) {
+ 				if (graph->commit->object.flags
+ 						& SYMMETRIC_LEFT)
+ 					strbuf_addch(sb, '<');
+ 				else
+ 					strbuf_addch(sb, '>');
+ 			}
 -			else if (graph->num_parents > 1)
++			else if (graph->commit->parents != NULL &&
++				 graph->commit->parents->next != NULL)
  				strbuf_addch(sb, 'M');
  			else
  				strbuf_addch(sb, '*');

[PATCH 1/2] Fix output of "git log --graph --boundary"

[Adam Simpkins]

Previously the graphing API wasn't aware of the revs->boundary flag, and
it always assumed that commits marked UNINTERESTING would not be
displayed.  As a result, the boundary commits were printed at the end of
the log output, but they didn't have any branch lines connecting them to
their children in the graph.

There was also another bug in the get_revision() code that caused
graph_update() to be called twice on the first boundary commit.  This
caused the graph API to think that a commit had been skipped, and print
a "..." line in the output.

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
 graph.c    |   94 ++++++++++++++++++++++++++++++++++++++++++------------------
 revision.c |    2 +-
 2 files changed, 67 insertions(+), 29 deletions(-)

diff --git a/graph.c b/graph.c
index 479035d..ce1abc0 100644
--- a/graph.c
+++ b/graph.c
@@ -191,9 +191,26 @@ static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
  * Returns 1 if the commit will be printed in the graph output,
  * and 0 otherwise.
  */
-static int graph_is_interesting(struct commit *commit)
+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.
+	 *
+	 * However, ignore the commit if SHOWN is set.  If SHOWN is set,
+	 * the commit is interesting, but it has already been printed.
+	 * This can happen because get_revision() doesn't return the
+	 * boundary commits in topological order, even when
+	 * revs->topo_order is set.
+	 */
+	if (graph->revs && graph->revs->boundary) {
+		if ((commit->object.flags & (SHOWN | CHILD_SHOWN)) ==
+		    CHILD_SHOWN)
+			return 1;
+	}
+
+	/*
 	 * Uninteresting and pruned commits won't be printed
 	 */
 	return (commit->object.flags & (UNINTERESTING | TREESAME)) ? 0 : 1;
@@ -208,7 +225,7 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 	/*
 	 * Ignore uinteresting commits
 	 */
-	if (!graph_is_interesting(commit))
+	if (!graph_is_interesting(graph, commit))
 		return;
 
 	/*
@@ -382,7 +399,7 @@ void graph_update(struct git_graph *graph, struct commit *commit)
 	 */
 	graph->num_parents = 0;
 	for (parent = commit->parents; parent; parent = parent->next) {
-		if (graph_is_interesting(parent->item))
+		if (graph_is_interesting(graph, parent->item))
 			graph->num_parents++;
 	}
 
@@ -545,6 +562,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;
@@ -570,31 +632,7 @@ void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)
 
 		if (col_commit == graph->commit) {
 			seen_this = 1;
-			/*
-			 * If revs->left_right is set, print the '<' or '>'
-			 * depending on which side this commit came from.
-			 *
-			 * If revs->left_right is not set and the commit is
-			 * a merge, print 'M'.  Otherwise, print '*'.
-			 *
-			 * 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->revs && graph->revs->left_right) {
-				if (graph->commit->object.flags
-						& SYMMETRIC_LEFT)
-					strbuf_addch(sb, '<');
-				else
-					strbuf_addch(sb, '>');
-			}
-			else if (graph->commit->parents != NULL &&
-				 graph->commit->parents->next != NULL)
-				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/revision.c b/revision.c
index 1341f3d..181fb0b 100644
--- a/revision.c
+++ b/revision.c
@@ -1697,7 +1697,7 @@ static struct commit *get_revision_internal(struct rev_info *revs)
 		 * switch to boundary commits output mode.
 		 */
 		revs->boundary = 2;
-		return get_revision(revs);
+		return get_revision_internal(revs);
 	}
 
 	/*
-- 
1.5.5.1.389.g35a9d

[PATCH 2/2] get_revision(): honor the topo_order flag for boundary commits

[Adam Simpkins]

Now get_revision() sorts the boundary commits when topo_order is set.
Since sort_in_topological_order() takes a struct commit_list, it first
places the boundary commits into revs->commits.

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---
 graph.c    |    9 +------
 revision.c |   73 ++++++++++++++++++++++++++++++++++++++++++++++-------------
 2 files changed, 58 insertions(+), 24 deletions(-)

diff --git a/graph.c b/graph.c
index ce1abc0..412b5ec 100644
--- a/graph.c
+++ b/graph.c
@@ -197,16 +197,9 @@ 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.
-	 *
-	 * However, ignore the commit if SHOWN is set.  If SHOWN is set,
-	 * the commit is interesting, but it has already been printed.
-	 * This can happen because get_revision() doesn't return the
-	 * boundary commits in topological order, even when
-	 * revs->topo_order is set.
 	 */
 	if (graph->revs && graph->revs->boundary) {
-		if ((commit->object.flags & (SHOWN | CHILD_SHOWN)) ==
-		    CHILD_SHOWN)
+		if (commit->object.flags & CHILD_SHOWN)
 			return 1;
 	}
 
diff --git a/revision.c b/revision.c
index 181fb0b..fb9924e 100644
--- a/revision.c
+++ b/revision.c
@@ -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,6 +1731,13 @@ static struct commit *get_revision_internal(struct rev_info *revs)
 		 * switch to boundary commits output mode.
 		 */
 		revs->boundary = 2;
+
+		/*
+		 * Update revs->commits to contain the list of
+		 * boundary commits.
+		 */
+		create_boundary_commit_list(revs);
+
 		return get_revision_internal(revs);
 	}
 
-- 
1.5.5.1.389.g35a9d

Re: [PATCH 1/2] Fix output of "git log --graph --boundary"

[Junio C Hamano]

Adam Simpkins <adam@adamsimpkins.net> writes:

> diff --git a/revision.c b/revision.c
> index 1341f3d..181fb0b 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -1697,7 +1697,7 @@ static struct commit *get_revision_internal(struct rev_info *revs)
>  		 * switch to boundary commits output mode.
>  		 */
>  		revs->boundary = 2;
> -		return get_revision(revs);
> +		return get_revision_internal(revs);
>  	}
>  
>  	/*

This hunk first got me worried, but this is a simple bugfix to 7fefda5
(log and rev-list: add --graph option, 2008-05-04) and does not break
callers without --graph option.

Looks good, thanks.