@@ -363,6 +363,14 @@ Default mode::
merges from the resulting history, as there are no selected
commits contributing to this merge.
+--simplify-forks::
+ Convert the commit graph into a spanning subgraph produced by a
+ depth-first-search of the history graph, searching the leftmost
+ parent first, and discarding edges to commits already visited.
+ Useful with `--graph` to visualize repositories with many merges
+ when you are interested in was added to master, and not when the
+ branch was last rebased.
+
--ancestry-path::
When given a range of commits to display (e.g. 'commit1..commit2'
or 'commit2 {caret}commit1'), only display commits that exist
@@ -2082,6 +2082,8 @@ 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, "--simplify-forks")) {
+ revs->simplify_forks = 1;
} else if (!strcmp(arg, "--date-order")) {
revs->sort_order = REV_SORT_BY_COMMIT_DATE;
revs->topo_order = 1;
@@ -3095,6 +3097,63 @@ static void simplify_merges(struct rev_info *revs)
}
}
+static void simplify_forks(struct rev_info *revs)
+{
+ struct commit_list *stack, *list_lr, *iter_list;
+ struct commit_list **parents;
+ struct commit *commit, *parent;
+
+ stack = NULL;
+ list_lr = NULL;
+
+ clear_object_flags(SIMP_FORK_VISITED);
+
+ for(iter_list = revs->commits; iter_list; iter_list = iter_list->next) {
+ /* process every commit to be displayed exactly once */
+ if(iter_list->item->object.flags & SIMP_FORK_VISITED)
+ continue;
+ clear_object_flags(SIMP_FORK_VISITING);
+ commit_list_insert(iter_list->item, &stack);
+ iter_list->item->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_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 & SIMP_FORK_VISITING) {
+ /* We have already visited this commit, from the same root.
+ * We do not explore it at all.
+ */
+ pop_commit(parents);
+ } else if(parent->object.flags & SIMP_FORK_VISITED) {
+ /* We visited this commit before, but from a different root.
+ * Leave it attached, but do not explore it further.
+ */
+ parents = &((*parents)->next);
+ } else {
+ /* We have not visited this commit yet. Explore it, as usual.
+ */
+ parent->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_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);
+ }
+ }
+ }
+
+ clear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING);
+}
+
static void set_children(struct rev_info *revs)
{
struct commit_list *l;
@@ -3392,10 +3451,16 @@ int prepare_revision_walk(struct rev_info *revs)
if (revs->limited) {
if (limit_list(revs) < 0)
return -1;
+ if (revs->simplify_forks)
+ simplify_forks(revs);
if (revs->topo_order)
sort_in_topological_order(&revs->commits, revs->sort_order);
- } else if (revs->topo_order)
+ } else if (revs->topo_order) {
+ if (revs->simplify_forks)
+ simplify_forks(revs);
init_topo_walk(revs);
+ } else if (revs->simplify_forks)
+ simplify_forks(revs);
if (revs->line_level_traverse)
line_log_filter(revs);
if (revs->simplify_merges)
@@ -51,6 +51,11 @@
#define TOPO_WALK_EXPLORED (1u<<27)
#define TOPO_WALK_INDEGREE (1u<<28)
+/* Re-use the TOPO_WALK flagspace for simplify_forks
+ */
+#define SIMP_FORK_VISITED (1u<<27)
+#define SIMP_FORK_VISITING (1u<<28)
+
#define DECORATE_SHORT_REFS 1
#define DECORATE_FULL_REFS 2
@@ -132,6 +137,7 @@ struct rev_info {
no_walk:2,
remove_empty_trees:1,
simplify_history:1,
+ simplify_forks:1,
show_pulls:1,
topo_order:1,
simplify_merges:1,
@@ -85,6 +85,28 @@ test_expect_success '--graph --all' '
test_cmp expected actual
'
+# Make sure that simplify_histpry_forks produces a spanning tree
+test_expect_success '--graph --simplify-forks --all' '
+ rm -f expected &&
+ echo "* $A7" >> expected &&
+ echo "* $A6" >> expected &&
+ echo "|\ " >> expected &&
+ echo "| * $C4" >> expected &&
+ echo "| * $C3" >> expected &&
+ echo "* $A5" >> expected &&
+ echo "*-. $A4" >> expected &&
+ echo "|\ \ " >> expected &&
+ echo "| | * $C2" >> expected &&
+ echo "| | * $C1" >> expected &&
+ echo "| * $B2" >> expected &&
+ echo "| * $B1" >> expected &&
+ echo "* $A3" >> expected &&
+ echo "* $A2" >> expected &&
+ echo "* $A1" >> expected &&
+ git rev-list --graph --simplify-forks --all > actual &&
+ test_cmp expected actual
+ '
+
# Make sure the graph_is_interesting() code still realizes
# that undecorated merges are interesting, even with --simplify-by-decoration
test_expect_success '--graph --simplify-by-decoration' '
@@ -157,6 +179,20 @@ test_expect_success '--graph --full-history -- bar.txt' '
test_cmp expected actual
'
+test_expect_success '--graph --simplify-forks --full-history -- bar.txt' '
+ rm -f expected &&
+ echo "* $A7" >> expected &&
+ echo "* $A6" >> expected &&
+ echo "|\\ " >> expected &&
+ echo "| * $C4" >> expected &&
+ echo "* $A5" >> expected &&
+ echo "* $A4" >> expected &&
+ echo "* $A3" >> expected &&
+ echo "* $A2" >> expected &&
+ git rev-list --graph --simplify-forks --full-history --all -- bar.txt > actual &&
+ test_cmp expected actual
+ '
+
test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '
rm -f expected &&
echo "* $A7" >> expected &&
@@ -172,6 +208,20 @@ test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '
test_cmp expected actual
'
+test_expect_success '--graph --simplify-forks --full-history --simplify-merges -- bar.txt' '
+ rm -f expected &&
+ echo "* $A7" >> expected &&
+ echo "* $A6" >> expected &&
+ echo "|\\ " >> expected &&
+ echo "| * $C4" >> expected &&
+ echo "* $A5" >> expected &&
+ echo "* $A3" >> expected &&
+ echo "* $A2" >> expected &&
+ git rev-list --graph --simplify-forks --full-history --simplify-merges --all \
+ -- bar.txt > actual &&
+ test_cmp expected actual
+ '
+
test_expect_success '--graph -- bar.txt' '
rm -f expected &&
echo "* $A7" >> expected &&