[PATCH 2/3 v3] Teach git-rev-list --ignore-merge-bases

[Antonio Russo <antonio.e.russo@gmail.com>]

This new option simplifies the graph of commits for merges.  Commits are
shown before their parents, but edges from those commits to commits
reachable from the first parent are removed.  Being disconnected from
the branch from which they were forked, these amputated merges
effectively lose all information about their merge base.

When used with --graph, this amputation can dramatically reduce the
width of the displayed graph and the total time taken to draw all
output.

The implementation traverses all reachable commits with a
depth-first-search to produce a spanning tree.

Signed-off-by: Antonio Russo <antonio.e.russo@gmail.com>
---
 Documentation/rev-list-options.txt |  9 ++++
 object.h                           |  2 +-
 revision.c                         | 85 ++++++++++++++++++++++++++++++
 revision.h                         |  5 ++
 4 files changed, 100 insertions(+), 1 deletion(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 04ad7dd36e..3f5d196985 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -363,6 +363,15 @@ Default mode::
 	merges from the resulting history, as there are no selected
 	commits contributing to this merge.

+--ignore-merge-bases::
+	Show commits that are introduced by each merge before showing
+	the first parent of the merge but remove edges from those commits
+	to commits reachable from the first parent. When used with
+	`--graph`, this can help visualize repositories with many merges
+	when you are not interested in the merge base used for each
+	merge. It also reduces the width of the graph visualization
+	when used with `--graph`.
+
 --ancestry-path::
 	When given a range of commits to display (e.g. 'commit1..commit2'
 	or 'commit2 {caret}commit1'), only display commits that exist
diff --git a/object.h b/object.h
index b22328b838..0bf6fb0d55 100644
--- a/object.h
+++ b/object.h
@@ -59,7 +59,7 @@ struct object_array {

 /*
  * object flag allocation:
- * revision.h:               0---------10         15                   25----28
+ * revision.h:               0---------10         15                   23----28
  * fetch-pack.c:             01
  * negotiator/default.c:       2--5
  * walker.c:                 0-2
diff --git a/revision.c b/revision.c
index 5bc96444b6..ae81175e34 100644
--- a/revision.c
+++ b/revision.c
@@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 		revs->simplify_by_decoration = 1;
 		revs->limited = 1;
 		revs->prune = 1;
+	} else if (!strcmp(arg, "--ignore-merge-bases")) {
+		revs->limited = 1;
+		revs->ignore_merge_bases = 1;
 	} else if (!strcmp(arg, "--date-order")) {
 		revs->sort_order = REV_SORT_BY_COMMIT_DATE;
 		revs->topo_order = 1;
@@ -3095,6 +3098,86 @@ static void simplify_merges(struct rev_info *revs)
 	}
 }

+static void cleanup_ignore_merge_bases(struct commit *commit) {
+	struct commit_list *stack;
+	struct commit_list *parents;
+	stack = NULL;
+
+	commit_list_insert(commit, &stack);
+	while (stack) {
+		commit = pop_commit(&stack);
+		commit->object.flags &= !IGN_MRG_BASES_VISITING;
+
+		parents = commit->parents;
+		for (parents = commit->parents; parents; parents = parents->next)
+			commit_list_insert(parents->item, &stack);
+	}
+}
+
+static void do_ignore_merge_bases(struct commit *commit) {
+	struct commit_list *stack, *list_lr;
+	struct commit_list **parents;
+	struct commit *parent;
+	stack = NULL;
+	list_lr = NULL;
+
+	/* process every commit to be displayed exactly once */
+	commit_list_insert(commit, &stack);
+	commit->object.flags |= IGN_MRG_BASES_VISITED | IGN_MRG_BASES_VISITING;
+	while (stack) {
+		commit = pop_commit(&stack);
+		/*
+		 * process the parent nodes: removing links to
+		 * commits already visited (creating a spanning tree)
+		 */
+		parents = &(commit->parents);
+		while (*parents) {
+			parent = (*parents)->item;
+			if (parent->object.flags & IGN_MRG_BASES_VISITING) {
+				/*
+				 * We have already visited this commit, from the same root.
+				 * We do not explore it at all.
+				 */
+				pop_commit(parents);
+				continue;
+			}
+			if (!(parent->object.flags & IGN_MRG_BASES_VISITED)) {
+				/*
+				 * If we visited this commit before, but from a different root,
+				 * leave it attached, but do not explore it further.
+				 *
+				 * If we have not visited this commit yet, explore it, as usual.
+				 */
+				parent->object.flags |= IGN_MRG_BASES_VISITED | IGN_MRG_BASES_VISITING;
+				commit_list_insert(parent, &list_lr);
+			}
+			parents = &((*parents)->next);
+		}
+
+		/*
+		 * Feed the parents, right to left (reversed) onto the
+		 * stack to do a depth-first traversal of the commit graph.
+		 */
+		while (list_lr)
+			commit_list_insert(pop_commit(&list_lr), &stack);
+	}
+}
+
+static void ignore_merge_bases(struct rev_info *revs)
+{
+	struct commit_list *iter_list;
+	struct commit *prev = NULL;
+
+	for (iter_list = revs->commits; iter_list; iter_list = iter_list->next) {
+		if (iter_list->item->object.flags & IGN_MRG_BASES_VISITED)
+			continue;
+		if (prev)
+			cleanup_ignore_merge_bases(prev);
+		prev = iter_list->item;
+		do_ignore_merge_bases(prev);
+	}
+}
+
 static void set_children(struct rev_info *revs)
 {
 	struct commit_list *l;
@@ -3392,6 +3475,8 @@ int prepare_revision_walk(struct rev_info *revs)
 	if (revs->limited) {
 		if (limit_list(revs) < 0)
 			return -1;
+		if (revs->ignore_merge_bases)
+			ignore_merge_bases(revs);
 		if (revs->topo_order)
 			sort_in_topological_order(&revs->commits, revs->sort_order);
 	} else if (revs->topo_order)
diff --git a/revision.h b/revision.h
index c1af164b30..93b318b304 100644
--- a/revision.h
+++ b/revision.h
@@ -37,6 +37,10 @@

 /* WARNING: This is also used as REACHABLE in commit-graph.c. */
 #define PULL_MERGE	(1u<<15)
+
+#define IGN_MRG_BASES_VISITED	(1u<<23)
+#define IGN_MRG_BASES_VISITING	(1u<<24)
+
 /*
  * Indicates object was reached by traversal. i.e. not given by user on
  * command-line or stdin.
@@ -132,6 +136,7 @@ struct rev_info {
 			no_walk:2,
 			remove_empty_trees:1,
 			simplify_history:1,
+			ignore_merge_bases:1,
 			show_pulls:1,
 			topo_order:1,
 			simplify_merges:1,
-- 
2.26.2