[PATCH 0/3] Ignore merge bases graph simplification

[PATCH 0/3] Ignore merge bases graph simplification

[Antonio Russo]

This patch series is a second attempt at providing a way to simplify the
graphical representation of forked branches that are merged back in.
Currently, when many branches are forked off the same commit, a
"mountain" of the tails of the merge that connect to the merge base
accumulate, making visual inspection of the --graph output challenging:

% git log --graph --oneline 20514004dd -n20

> * 20514004dd Start the post 2.27 cycle
> *   54041832d7 Merge branch 'en/fast-import-looser-date'
> |\
> | * d42a2fb72f fast-import: add new --date-format=raw-permissive format
> * |   a0ba2bbbdd Merge branch 'mt/zsh-completion-optim'
> |\ \
> | * | a44a0a9fc4 completion: use native ZSH array pattern matching
> * | |   e34df9a6e5 Merge branch 'la/diff-relative-config'
> |\ \ \
> | * | | c28ded83fc diff: add config option relative
> * | | |   de82fb45db Merge branch 'rs/checkout-b-track-error'
> |\ \ \ \
> | * | | | bb2198fb91 checkout: improve error messages for -b with extra argument
> | * | | | 16ab794b82 checkout: add tests for -b and --track
> * | | | |   202a2b8e71 Merge branch 'lo/sparse-universal-zero-init'
> |\ \ \ \ \
> | * | | | | 1c96642326 sparse: allow '{ 0 }' to be used without warnings
> | | |_|_|/
> | |/| | |
> * | | | |   1ab0dfde2c Merge branch 'cb/t5608-cleanup'
> |\ \ \ \ \
> | * | | | | d63ae31962 t5608: avoid say() and use "skip_all" instead for consistency
> | |/ / / /
> * | | | |   70a1e331b0 Merge branch 'jx/pkt-line-doc-count-fix'
> |\ \ \ \ \
> | * | | | | 2c31a7aa44 doc: fix wrong 4-byte length of pkt-line message
> | |/ / / /
> * | | | |   51b4708811 Merge branch 'jn/experimental-opts-into-proto-v2'
> |\ \ \ \ \
> | * | | | | 3697caf4b9 config: let feature.experimental imply protocol.version=2
> * | | | | |   7a8fec908a Merge branch 'bk/p4-prepare-p4-only-fix'
> |\ \ \ \ \ \
> | * | | | | | 2dfdd705ff git-p4.py: fix --prepare-p4-only error with multiple commits

This patch adds a new "--ignore-merge-bases' parameter that, roughly,
hides all of the information about the merge base:

% git log --graph --oneline 20514004dd --ignore-merge-bases -n20

> * 20514004dd Start the post 2.27 cycle
> *   54041832d7 Merge branch 'en/fast-import-looser-date'
> |\
> | * d42a2fb72f fast-import: add new --date-format=raw-permissive format
> *   a0ba2bbbdd Merge branch 'mt/zsh-completion-optim'
> |\
> | * a44a0a9fc4 completion: use native ZSH array pattern matching
> *   e34df9a6e5 Merge branch 'la/diff-relative-config'
> |\
> | * c28ded83fc diff: add config option relative
> *   de82fb45db Merge branch 'rs/checkout-b-track-error'
> |\
> | * bb2198fb91 checkout: improve error messages for -b with extra argument
> | * 16ab794b82 checkout: add tests for -b and --track
> *   202a2b8e71 Merge branch 'lo/sparse-universal-zero-init'
> |\
> | * 1c96642326 sparse: allow '{ 0 }' to be used without warnings
> *   1ab0dfde2c Merge branch 'cb/t5608-cleanup'
> |\
> | * d63ae31962 t5608: avoid say() and use "skip_all" instead for consistency
> *   70a1e331b0 Merge branch 'jx/pkt-line-doc-count-fix'
> |\
> | * 2c31a7aa44 doc: fix wrong 4-byte length of pkt-line message
> *   51b4708811 Merge branch 'jn/experimental-opts-into-proto-v2'
> |\
> | * 3697caf4b9 config: let feature.experimental imply protocol.version=2
> *   7a8fec908a Merge branch 'bk/p4-prepare-p4-only-fix'
> |\
> | * 2dfdd705ff git-p4.py: fix --prepare-p4-only error with multiple commits

The significant changes since the last round of discussion are:

1. A streaming version of the algorithm has been implemented.  No longer
is revs->limited, with all of its very serious drawbacks, required.

2. The commit->parents commit_list is no longer modified (amputated).
Instead, a "principle child" is identified during a (heavily modified)
indegree walk.

3. Per D. Stolee's suggestion, the output of child->parent edges are
suppressed during graph emission (in particular, in
graph_is_interesting).

4. No commit flags are used. All per-commit ancillary data is stored
in a commit slab.

I discarded J. Sixt's suggestion to change the format of the --boundary
output.  While I like the proposed format, I think the change is
orthogonal to this (already large) change.

There are several outstanding issues that I would appreciate help with:

1. I have developed some terminology to think about the concepts used
here.  They are definitely not conventional, and probably should be
changed.  I would appreciate feedback:

 - A "skeleton walk" is the streaming version of a left-first
   DFS-generated spanning tree.  This is achieved using a carefully
   generation-limited traversal of the commit graph.  *Edges* are
   stored in a skel_walk_list structure.  This traversal should be
   linear in the number of edges (but I'll admit I haven't actually
   done this proof).

 - The "guide commits" are all of the commits in revs->commits.

 - A "component" (and this is particularly bad terminology) is the
   collection of commits reachable from a guide commit, but not from
   an earlier ("higher priority") guide commit.

   This approach avoids any ambiguity in the output of
   --ignore-merge-bases as to what commits are included at the merge
   point, by always drawing any edge between components.  Notice that
   the definition of a component means that no edges go from higher-
   priority to lower-priority components (instead, those commits are
   absorbed into the higher-priority component).

 - The "principle child" of a commit c is the first child in the
   leftmost-first DFS that references c.  It is always in the same
   component as c, and it is the only commit in that component whose
   edge is drawn connecting to c.

Presumably, all of these terms should be documented (with visuals)
somewhere.  If there is serious interest in this patch, I'm happy to do
this, but I'm loathe to waste time doing this until I start hearing some
sort of positive feedback on what has become a significant time sink.

2. The meat of the changes are monolithically collected into patch 2/3.
It does not make sense in my mind to implement functions that are not
used anywhere, and then make first use them in another commit.  But, I
can split this up into the skeleton walk implementation and the graph
display, if wanted.

3. A skel_walk_info structure is allocated at parameter parse time, and
currently is never freed.  While this is certainly a memory leak, it is
not clear to me if there is a benefit to performing the cleanup, besides
getting clean valgrind output (and masking more serious memory leaks). I
I didn't try to read everything in Documentation, but, besides an
abundance of commits fixing memory leaks, I could not find a specific
policy regarding freeing memory before program termination.

4. The implementation for revs->limited and !revs->limited is
frustratingly similar, but I cannot see any particular elegant way to
deduplicate the code.  The existing code also seems to suffer similarly.

Is there movement forward on eliminating the whole rev->limited
code-path?  This is obviously out of scope for this patch set, but
maintaining two code-paths was a hassle for this one action, and I can
imagine that it is much worse when multiplied by all of git's features.

5. Similarly, the skel_walk is very similar to the existing indegree
walk.  But again, avoiding duplicated code leads to uncomfortable

> if (skel) {
>         ...
> }

blocks.  It also confuses gcc, which has trouble realizing that
variables were initialized in previous `if (skel)` blocks.  I'm then
forced to resort to underhanded tricks: blanket initializing of
variables that should have been optimized out if !skel.

Duplicating the entire function leads to cleaner and negligibly faster
code.  Frustratingly, but unsurprisingly, the meticulous careful
skeleton walk that I've implemented is slightly slower than the
existing indegree walk, so it's a bad candidate to replace the old code.

Any thoughts?

The entire patch set is also available at [1], which includes a few
debugging assertions enabled, and the excision of the unused
free_skel_info method (see 3, above) which otherwise breaks
-Wunused-function.  It passes the full battery of tests there (as well
as locally for me).

Best,
Antonio Russo

[1] <https://github.com/aerusso/git/tree/mrs/imb-skel>

[PATCH 1/3] Clean up t6016-rev-list-graph-simplify-history

[Antonio Russo]

Simplifies the logic used to test rev-list, making adding new tests
easier.  Uses a heredoc and sed expansion of the expected output,
instead of shell substitutions and manually escaped echo's.

Reviewed-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Antonio Russo <antonio.e.russo@gmail.com>
---
 t/t6016-rev-list-graph-simplify-history.sh | 350 ++++++++++-----------
 1 file changed, 167 insertions(+), 183 deletions(-)

diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh
index f5e6e92f5b..b6b2ab33ab 100755
--- a/t/t6016-rev-list-graph-simplify-history.sh
+++ b/t/t6016-rev-list-graph-simplify-history.sh
@@ -9,6 +9,13 @@ test_description='--graph and simplified history'

 . ./test-lib.sh

+check_graph () {
+	sed -f expand_tag_to_oid.sed >expect &&
+	git rev-list --graph "$@" >actual &&
+	sed 's/ *$//' actual >actual.sanitized &&
+	test_cmp expect actual.sanitized
+}
+
 test_expect_success 'set up rev-list --graph test' '
 	# 3 commits on branch A
 	test_commit A1 foo.txt &&
@@ -43,76 +50,62 @@ test_expect_success 'set up rev-list --graph test' '

 	test_commit A7 bar.txt &&

-	# Store commit names in variables for later use
-	A1=$(git rev-parse --verify A1) &&
-	A2=$(git rev-parse --verify A2) &&
-	A3=$(git rev-parse --verify A3) &&
-	A4=$(git rev-parse --verify A4) &&
-	A5=$(git rev-parse --verify A5) &&
-	A6=$(git rev-parse --verify A6) &&
-	A7=$(git rev-parse --verify A7) &&
-	B1=$(git rev-parse --verify B1) &&
-	B2=$(git rev-parse --verify B2) &&
-	C1=$(git rev-parse --verify C1) &&
-	C2=$(git rev-parse --verify C2) &&
-	C3=$(git rev-parse --verify C3) &&
-	C4=$(git rev-parse --verify C4)
-	'
+	git for-each-ref --format="s/%(refname:short)/%(objectname)/" \
+		refs/tags >expand_tag_to_oid.sed
+'

 test_expect_success '--graph --all' '
-	rm -f expected &&
-	echo "* $A7" >> expected &&
-	echo "*   $A6" >> expected &&
-	echo "|\\  " >> expected &&
-	echo "| * $C4" >> expected &&
-	echo "| * $C3" >> expected &&
-	echo "* | $A5" >> expected &&
-	echo "| |   " >> expected &&
-	echo "|  \\  " >> expected &&
-	echo "*-. | $A4" >> expected &&
-	echo "|\\ \\| " >> expected &&
-	echo "| | * $C2" >> expected &&
-	echo "| | * $C1" >> expected &&
-	echo "| * | $B2" >> expected &&
-	echo "| * | $B1" >> expected &&
-	echo "* | | $A3" >> expected &&
-	echo "| |/  " >> expected &&
-	echo "|/|   " >> expected &&
-	echo "* | $A2" >> expected &&
-	echo "|/  " >> expected &&
-	echo "* $A1" >> expected &&
-	git rev-list --graph --all > actual &&
-	test_cmp expected actual
-	'
+	check_graph --all <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	| * C3
+	* | A5
+	| |
+	|  \
+	*-. | A4
+	|\ \|
+	| | * C2
+	| | * C1
+	| * | B2
+	| * | B1
+	* | | A3
+	| |/
+	|/|
+	* | A2
+	|/
+	* A1
+	EOF
+'

 # 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' '
-	rm -f expected &&
 	git tag -d A4 &&
-	echo "* $A7" >> expected &&
-	echo "*   $A6" >> expected &&
-	echo "|\\  " >> expected &&
-	echo "| * $C4" >> expected &&
-	echo "| * $C3" >> expected &&
-	echo "* | $A5" >> expected &&
-	echo "| |   " >> expected &&
-	echo "|  \\  " >> expected &&
-	echo "*-. | $A4" >> expected &&
-	echo "|\\ \\| " >> expected &&
-	echo "| | * $C2" >> expected &&
-	echo "| | * $C1" >> expected &&
-	echo "| * | $B2" >> expected &&
-	echo "| * | $B1" >> expected &&
-	echo "* | | $A3" >> expected &&
-	echo "| |/  " >> expected &&
-	echo "|/|   " >> expected &&
-	echo "* | $A2" >> expected &&
-	echo "|/  " >> expected &&
-	echo "* $A1" >> expected &&
-	git rev-list --graph --all --simplify-by-decoration > actual &&
-	test_cmp expected actual
-	'
+	check_graph --all --simplify-by-decoration <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	| * C3
+	* | A5
+	| |
+	|  \
+	*-. | A4
+	|\ \|
+	| | * C2
+	| | * C1
+	| * | B2
+	| * | B1
+	* | | A3
+	| |/
+	|/|
+	* | A2
+	|/
+	* A1
+	EOF
+'

 test_expect_success 'setup: get rid of decorations on B' '
 	git tag -d B2 &&
@@ -122,142 +115,133 @@ test_expect_success 'setup: get rid of decorations on B' '

 # Graph with branch B simplified away
 test_expect_success '--graph --simplify-by-decoration prune branch B' '
-	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 "* | $A3" >> expected &&
-	echo "|/  " >> expected &&
-	echo "* $A2" >> expected &&
-	echo "* $A1" >> expected &&
-	git rev-list --graph --simplify-by-decoration --all > actual &&
-	test_cmp expected actual
-	'
+	check_graph --simplify-by-decoration --all <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	| * C3
+	* | A5
+	* | A4
+	|\|
+	| * C2
+	| * C1
+	* | A3
+	|/
+	* A2
+	* A1
+	EOF
+'

 test_expect_success '--graph --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 "|\\| " >> expected &&
-	echo "* | $A3" >> expected &&
-	echo "|/  " >> expected &&
-	echo "* $A2" >> expected &&
-	git rev-list --graph --full-history --all -- bar.txt > actual &&
-	test_cmp expected actual
-	'
+	check_graph --full-history --all -- bar.txt <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	* | A5
+	* | A4
+	|\|
+	* | A3
+	|/
+	* A2
+	EOF
+'

 test_expect_success '--graph --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 "|/  " >> expected &&
-	echo "* $A2" >> expected &&
-	git rev-list --graph --full-history --simplify-merges --all \
-		-- bar.txt > actual &&
-	test_cmp expected actual
-	'
+	check_graph --full-history --simplify-merges --all -- bar.txt <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	* | A5
+	* | A3
+	|/
+	* A2
+	EOF
+'

 test_expect_success '--graph -- bar.txt' '
-	rm -f expected &&
-	echo "* $A7" >> expected &&
-	echo "* $A5" >> expected &&
-	echo "* $A3" >> expected &&
-	echo "| * $C4" >> expected &&
-	echo "|/  " >> expected &&
-	echo "* $A2" >> expected &&
-	git rev-list --graph --all -- bar.txt > actual &&
-	test_cmp expected actual
-	'
+	check_graph --all -- bar.txt <<-\EOF
+	* A7
+	* A5
+	* A3
+	| * C4
+	|/
+	* A2
+	EOF
+'

 test_expect_success '--graph --sparse -- bar.txt' '
-	rm -f expected &&
-	echo "* $A7" >> expected &&
-	echo "* $A6" >> expected &&
-	echo "* $A5" >> expected &&
-	echo "* $A4" >> expected &&
-	echo "* $A3" >> expected &&
-	echo "| * $C4" >> expected &&
-	echo "| * $C3" >> expected &&
-	echo "| * $C2" >> expected &&
-	echo "| * $C1" >> expected &&
-	echo "|/  " >> expected &&
-	echo "* $A2" >> expected &&
-	echo "* $A1" >> expected &&
-	git rev-list --graph --sparse --all -- bar.txt > actual &&
-	test_cmp expected actual
-	'
+	check_graph --sparse --all -- bar.txt <<-\EOF
+	* A7
+	* A6
+	* A5
+	* A4
+	* A3
+	| * C4
+	| * C3
+	| * C2
+	| * C1
+	|/
+	* A2
+	* A1
+	EOF
+'

 test_expect_success '--graph ^C4' '
-	rm -f expected &&
-	echo "* $A7" >> expected &&
-	echo "* $A6" >> expected &&
-	echo "* $A5" >> expected &&
-	echo "*   $A4" >> expected &&
-	echo "|\\  " >> expected &&
-	echo "| * $B2" >> expected &&
-	echo "| * $B1" >> expected &&
-	echo "* $A3" >> expected &&
-	git rev-list --graph --all ^C4 > actual &&
-	test_cmp expected actual
-	'
+	check_graph --all ^C4 <<-\EOF
+	* A7
+	* A6
+	* A5
+	*   A4
+	|\
+	| * B2
+	| * B1
+	* A3
+	EOF
+'

 test_expect_success '--graph ^C3' '
-	rm -f expected &&
-	echo "* $A7" >> expected &&
-	echo "*   $A6" >> expected &&
-	echo "|\\  " >> expected &&
-	echo "| * $C4" >> expected &&
-	echo "* $A5" >> expected &&
-	echo "*   $A4" >> expected &&
-	echo "|\\  " >> expected &&
-	echo "| * $B2" >> expected &&
-	echo "| * $B1" >> expected &&
-	echo "* $A3" >> expected &&
-	git rev-list --graph --all ^C3 > actual &&
-	test_cmp expected actual
-	'
+	check_graph --all ^C3 <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	* A5
+	*   A4
+	|\
+	| * B2
+	| * B1
+	* A3
+	EOF
+'

 # I don't think the ordering of the boundary commits is really
 # that important, but this test depends on it.  If the ordering ever changes
 # in the code, we'll need to update this test.
 test_expect_success '--graph --boundary ^C3' '
-	rm -f expected &&
-	echo "* $A7" >> expected &&
-	echo "*   $A6" >> expected &&
-	echo "|\\  " >> expected &&
-	echo "| * $C4" >> expected &&
-	echo "* | $A5" >> expected &&
-	echo "| |     " >> expected &&
-	echo "|  \\    " >> expected &&
-	echo "*-. \\   $A4" >> expected &&
-	echo "|\\ \\ \\  " >> expected &&
-	echo "| * | | $B2" >> expected &&
-	echo "| * | | $B1" >> expected &&
-	echo "* | | | $A3" >> expected &&
-	echo "o | | | $A2" >> expected &&
-	echo "|/ / /  " >> expected &&
-	echo "o / / $A1" >> expected &&
-	echo " / /  " >> expected &&
-	echo "| o $C3" >> expected &&
-	echo "|/  " >> expected &&
-	echo "o $C2" >> expected &&
-	git rev-list --graph --boundary --all ^C3 > actual &&
-	test_cmp expected actual
-	'
+	check_graph --boundary --all ^C3 <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	* | A5
+	| |
+	|  \
+	*-. \   A4
+	|\ \ \
+	| * | | B2
+	| * | | B1
+	* | | | A3
+	o | | | A2
+	|/ / /
+	o / / A1
+	 / /
+	| o C3
+	|/
+	o C2
+	EOF
+'

 test_done
-- 
2.27.0

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

[Antonio Russo]

This new option simplifies the graph of commits for merges.  Edges to
commits reachable from more leftward parents, or more leftward parents
of recursive child commits, are removed.  This "skeleton" spanning tree
effectively omits all information about merge bases.

When multiple tip commits are specified, all commits reachable from each
tip commit (but not earlier tips) are simplified as above to form a
"component".  All edges between components are displayed.

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

Signed-off-by: Antonio Russo <antonio.e.russo@gmail.com>
---
 Documentation/rev-list-options.txt |  13 ++
 builtin/log.c                      |   2 +-
 builtin/show-branch.c              |   2 +-
 commit.c                           | 132 +++++++++++++---
 commit.h                           |   4 +-
 graph.c                            |  40 +++--
 revision.c                         | 240 +++++++++++++++++++++++++++--
 revision.h                         |  17 ++
 8 files changed, 404 insertions(+), 46 deletions(-)

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

+--ignore-merge-bases::
+	Simplify merges by removing edges to commits reachable from
+	more leftware parents, or more leftward parents of recursive
+	children. 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`.
+
+	When multiple tip commits are specified, all commits reachable
+	from each tip commit (but not earlier tips) are simplified as
+	above to form a "component".  All edges between components are
+	displayed.
+
 --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/builtin/log.c b/builtin/log.c
index d104d5c688..2883fa2872 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -306,7 +306,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)
 	int show_header = 1;

 	revs->diffopt.close_file = 0;
-	sort_in_topological_order(&list, revs->sort_order);
+	sort_in_topological_order(&list, NULL, revs->sort_order);
 	while (list && i) {
 		struct commit *commit = list->item;
 		switch (simplify_commit(revs, commit)) {
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index 7e52ee9126..c766d61126 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -903,7 +903,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 		exit(0);

 	/* Sort topologically */
-	sort_in_topological_order(&seen, sort_order);
+	sort_in_topological_order(&seen, NULL, sort_order);

 	/* Give names to commits */
 	if (!sha1_name && !no_name)
diff --git a/commit.c b/commit.c
index 87686a7055..aa5ff43c78 100644
--- a/commit.c
+++ b/commit.c
@@ -758,14 +758,18 @@ int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)
 /*
  * Performs an in-place topological sort on the list supplied.
  */
-void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order)
+void sort_in_topological_order(struct commit_list **list,
+			       struct skel_info *skel,
+			       enum rev_sort_order sort_order)
 {
 	struct commit_list *next, *orig = *list;
 	struct commit_list **pptr;
 	struct indegree_slab indegree;
-	struct prio_queue queue;
-	struct commit *commit;
+	struct prio_queue queue, revqueue;
+	struct commit *commit, *parent;
 	struct author_date_slab author_date;
+	int *comp_p = NULL, *comp_c = NULL, next_comp = 1;
+	struct skel_datum *d_p = NULL, *d_c = NULL;

 	if (!orig)
 		return;
@@ -773,20 +777,10 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so

 	init_indegree_slab(&indegree);
 	memset(&queue, '\0', sizeof(queue));
+	memset(&revqueue, '\0', sizeof(revqueue));

-	switch (sort_order) {
-	default: /* REV_SORT_IN_GRAPH_ORDER */
-		queue.compare = NULL;
-		break;
-	case REV_SORT_BY_COMMIT_DATE:
-		queue.compare = compare_commits_by_commit_date;
-		break;
-	case REV_SORT_BY_AUTHOR_DATE:
+	if (sort_order == REV_SORT_BY_AUTHOR_DATE)
 		init_author_date_slab(&author_date);
-		queue.compare = compare_commits_by_author_date;
-		queue.cb_data = &author_date;
-		break;
-	}

 	/* Mark them and clear the indegree */
 	for (next = orig; next; next = next->next) {
@@ -795,19 +789,100 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so
 		/* also record the author dates, if needed */
 		if (sort_order == REV_SORT_BY_AUTHOR_DATE)
 			record_author_date(&author_date, commit);
+		prio_queue_put(&queue, commit);
 	}

+	/*
+	 * When performing a skeleton walk, all commits must be processed from
+	 * highest priority to lowest priority.  The highest priority commits
+	 * appear first in orig, so we must reverse the queue to ensure they
+	 * are processed first.
+	 */
+	if (skel)
+		prio_queue_reverse(&queue);
+
 	/* update the indegree */
-	for (next = orig; next; next = next->next) {
-		struct commit_list *parents = next->item->parents;
-		while (parents) {
+	while ((commit = prio_queue_get(&queue)) != NULL) {
+		if (skel) {
+			comp_c = &skel_slab_at(&skel->slab, commit)->component;
+
+			/*
+			 * Store if we have visited the commit in its sign bit.
+			 *
+			 * Skip if we already visited, or mark that this commit
+			 * has been visisted.
+			 *
+			 * Assign a new component if none has already been
+			 * propagated to the commit.
+			 */
+			if (*comp_c > 0)
+				continue;
+
+			if (!*comp_c)
+				*comp_c = next_comp++;
+			else
+				*comp_c = -*comp_c;
+		}
+
+		for (struct commit_list *parents = commit->parents;
+		     parents; parents = parents->next) {
 			struct commit *parent = parents->item;
 			int *pi = indegree_slab_at(&indegree, parent);

-			if (*pi)
+			if (!*pi)
+				continue;
+
+			if (skel) {
+				d_p = skel_slab_at(&skel->slab, parent);
+				/*
+				 * Back-propagate the child's component, and
+				 * mark the principle child.
+				 *
+				 * Only count the first intra-component
+				 * reference. but count all inter-component
+				 * references.
+				 *
+				 * Override lower-priorty (higher numerical
+				 * value) components.
+				 */
+				comp_p = &d_p->component;
+				if (!*comp_p || *comp_p > *comp_c) {
+					*comp_p = -*comp_c;
+					d_p->child = commit;
+					prio_queue_put(&revqueue, parent);
+					(*pi)++;
+				} else if (*comp_p < *comp_c)
+					(*pi)++;
+			} else
 				(*pi)++;
-			parents = parents->next;
 		}
+
+		/*
+		 * More leftward commits are higher priority, and therefore
+		 * must be processed first.
+		 */
+		if (skel)
+			while ((parent = prio_queue_get(&revqueue)) != NULL)
+				prio_queue_put(&queue, parent);
+	}
+
+	if (skel) {
+		clear_prio_queue(&revqueue);
+		clear_prio_queue(&queue);
+	}
+
+	/* reuse the priority queue */
+	switch (sort_order) {
+	default: /* REV_SORT_IN_GRAPH_ORDER */
+		queue.compare = NULL;
+		break;
+	case REV_SORT_BY_COMMIT_DATE:
+		queue.compare = compare_commits_by_commit_date;
+		break;
+	case REV_SORT_BY_AUTHOR_DATE:
+		queue.compare = compare_commits_by_author_date;
+		queue.cb_data = &author_date;
+		break;
 	}

 	/*
@@ -838,10 +913,18 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so
 	*list = NULL;
 	while ((commit = prio_queue_get(&queue)) != NULL) {
 		struct commit_list *parents;
+		if (skel) {
+			d_c = skel_slab_at(&skel->slab, commit);
+			comp_c = &d_c->component;
+		}

 		for (parents = commit->parents; parents ; parents = parents->next) {
 			struct commit *parent = parents->item;
 			int *pi = indegree_slab_at(&indegree, parent);
+			if (skel) {
+				d_p = skel_slab_at(&skel->slab, parent);
+				comp_p = &d_p->component;
+			}

 			if (!*pi)
 				continue;
@@ -850,9 +933,14 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so
 			 * parents are only enqueued for emission
 			 * when all their children have been emitted thereby
 			 * guaranteeing topological order.
+			 *
+			 * If we are performing a skeleton walk, do not count
+			 * intra-component references that are not from the
+			 * principle child.
 			 */
-			if (--(*pi) == 1)
-				prio_queue_put(&queue, parent);
+			if (!skel || (*comp_p != *comp_c || d_p->child == commit))
+				if (--(*pi) == 1)
+					prio_queue_put(&queue, parent);
 		}
 		/*
 		 * all children of commit have already been
diff --git a/commit.h b/commit.h
index 1b2dea5d85..64d04d124f 100644
--- a/commit.h
+++ b/commit.h
@@ -183,6 +183,7 @@ struct commit_list *copy_commit_list(struct commit_list *list);
 void free_commit_list(struct commit_list *list);

 struct rev_info; /* in revision.h, it circularly uses enum cmit_fmt */
+struct skel_info;

 int has_non_ascii(const char *text);
 const char *logmsg_reencode(const struct commit *commit,
@@ -226,7 +227,8 @@ enum rev_sort_order {
  *                            chain together.
  *   REV_SORT_BY_COMMIT_DATE: show eligible commits in committer-date order.
  */
-void sort_in_topological_order(struct commit_list **, enum rev_sort_order);
+void sort_in_topological_order(struct commit_list **, struct skel_info *,
+			       enum rev_sort_order);

 struct commit_graft {
 	struct object_id oid;
diff --git a/graph.c b/graph.c
index 4cd9915075..57fd51fb05 100644
--- a/graph.c
+++ b/graph.c
@@ -428,21 +428,43 @@ static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
  */
 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;
+	struct skel_datum *dat_p, *dat_c;
+	struct rev_info *revs = graph->revs;
+	struct skel_info *skel = NULL;
+
+	if (revs->ignore_merge_bases)
+		skel = revs->skel_info;
+
+	if (revs) {
+		/*
+		 * 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 (revs->boundary) {
+			if (commit->object.flags & CHILD_SHOWN)
+				return 1;
+		}
+
+		/*
+		 * If revs->ignore_merge_bases is set, suppress intra-component
+		 * edges that are not from the principle child.
+		 */
+		if (skel) {
+			dat_p = skel_slab_at(&skel->slab, commit);
+			dat_c = skel_slab_at(&skel->slab, graph->commit);
+			if (dat_p->component == dat_c->component &&
+			    dat_p->child != graph->commit) {
+				return 0;
+			}
+		}
 	}

 	/*
 	 * Otherwise, use get_commit_action() to see if this commit is
 	 * interesting
 	 */
-	return get_commit_action(graph->revs, commit) == commit_show;
+	return get_commit_action(revs, commit) == commit_show;
 }

 static struct commit_list *next_interesting_parent(struct git_graph *graph,
diff --git a/revision.c b/revision.c
index 60cca8c0b9..af676fd847 100644
--- a/revision.c
+++ b/revision.c
@@ -39,6 +39,22 @@ static const char *term_good;

 implement_shared_commit_slab(revision_sources, char *);

+implement_shared_commit_slab(skel_slab, struct skel_datum);
+
+static struct skel_info *new_skel_info(void)
+{
+	struct skel_info *info = xcalloc(1, sizeof(struct skel_info));
+	memset(info, '\0', sizeof(struct skel_info));
+	init_skel_slab(&info->slab);
+	return info;
+}
+
+static void free_skel_info(struct skel_info *info)
+{
+	clear_skel_slab(&info->slab);
+	free(info);
+}
+
 void show_object_with_name(FILE *out, struct object *obj, const char *name)
 {
 	const char *p;
@@ -2204,6 +2220,10 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 	} else if (!strcmp(arg, "--topo-order")) {
 		revs->sort_order = REV_SORT_IN_GRAPH_ORDER;
 		revs->topo_order = 1;
+	} else if (!strcmp(arg, "--ignore-merge-bases")) {
+		revs->topo_order = 1;
+		revs->ignore_merge_bases = 1;
+		revs->skel_info = new_skel_info();
 	} else if (!strcmp(arg, "--simplify-merges")) {
 		revs->simplify_merges = 1;
 		revs->topo_order = 1;
@@ -3348,14 +3368,179 @@ static void indegree_walk_step(struct rev_info *revs)
 	}
 }

+/*
+ * The skeleton walk is over edges in a graph.  Notationally, we refer to the
+ * commit (item) and the child, because we will be interested in the parents of
+ * item, not the children of child.
+ */
+struct skel_walk_list {
+	struct commit *item;
+	struct skel_walk_list *next;
+	struct commit *child;
+};
+
+static void swl_pop(struct skel_walk_list **stack)
+{
+	struct skel_walk_list *top = *stack;
+
+	if (top) {
+		*stack = top->next;
+		free(top);
+	}
+	return;
+}
+
+static struct skel_walk_list **swl_append(struct commit *item,
+					 struct commit *child,
+					 struct skel_walk_list **list_p)
+{
+	struct skel_walk_list *new_list = xmalloc(sizeof(struct skel_walk_list));
+
+	if (parse_commit_gently(item, 1) < 0) {
+		printf("WHAT!\n");
+		return list_p; //XXX: !!?
+	}
+
+	new_list->item = item;
+	new_list->next = *list_p;
+	new_list->child = child;
+
+	*list_p = new_list;
+	return &new_list->next;
+}
+
+static void skel_walk_step(struct rev_info *revs,
+			   struct skel_walk_list **next)
+{
+	struct indegree_slab *indegree = &revs->topo_walk_info->indegree;
+	struct skel_info *skel = revs->skel_info;
+	struct commit *commit = (*next)->item;
+	struct skel_datum *d_i = skel_slab_at(&skel->slab, commit);
+	int comp_c, first = 1;
+
+	explore_to_depth(revs, commit->generation);
+
+	/*
+	 * If the commit has already been visited, all the parents have already
+	 * been processed, but we still must count inter-component references.
+	 */
+	if (d_i->component) {
+		if ((*next)->child) {
+			comp_c = skel_slab_at(&skel->slab, (*next)->child)->component;
+
+			if (d_i->component < comp_c)
+				(*indegree_slab_at(indegree, commit))++;
+		}
+
+		swl_pop(next);
+		return;
+	}
+
+	/*
+	 * We are visiting commit for the first time:
+	 *  - count the indegree
+	 *  - mark the principle child
+	 *  - back-propagate the component
+	 *
+	 * If there is no principle child, allocate a new component.
+	 */
+	if (!(*next)->child)
+		d_i->component = skel->next_comp++;
+	else {
+		d_i->child = (*next)->child;
+		d_i->component = skel_slab_at(&skel->slab, d_i->child)->component;
+		*indegree_slab_at(indegree, commit) = 2;
+	}
+
+	/*
+	 * Push all parents onto the skeleton walk list, replacing *next.
+	 */
+	for (struct commit_list *parents = commit->parents;
+	     parents; parents = parents->next) {
+		struct commit *parent = parents->item;
+
+		/*
+		 * Micro-optimization to reuse the skeleton walk list entry,
+		 * if possible.
+		 */
+		if (first) {
+			(*next)->item = parent;
+			(*next)->child = commit;
+
+			next = &(*next)->next;
+			first = 0;
+		} else
+			next = swl_append(parent, commit, next);
+
+		if (revs->first_parent_only)
+			return;
+	}
+
+	if (first)
+		swl_pop(next);
+
+	return;
+}
+
 static void compute_indegrees_to_depth(struct rev_info *revs,
 				       uint32_t gen_cutoff)
 {
 	struct topo_walk_info *info = revs->topo_walk_info;
 	struct commit *c;
-	while ((c = prio_queue_peek(&info->indegree_queue)) &&
-	       c->generation >= gen_cutoff)
-		indegree_walk_step(revs);
+	struct skel_info *skel = NULL;
+	struct skel_walk_list **next;
+	uint32_t t, p_gen_cutoff = gen_cutoff;
+
+	if (revs->ignore_merge_bases)
+		skel = revs->skel_info;
+
+	if (!skel) {
+		while ((c = prio_queue_peek(&info->indegree_queue)) &&
+		       c->generation >= gen_cutoff)
+			indegree_walk_step(revs);
+		return;
+	}
+
+	/*
+	 * Explore all edges originating from commits of appropriate generation
+	 */
+	next = &skel->walk;
+	while (*next) {
+		if ((*next)->item->generation < gen_cutoff) {
+			/*
+			 * Ideally, we would explore this edge right now, but
+			 * we cannot, because we have not yet necessarily
+			 * explored more leftward commits to this depth.
+			 *
+			 * Notice that (*next)->child is not NULL, because we
+			 * always perform an initial search with depth of the
+			 * maximum of all tip commits.
+			 */
+			if ((*next)->child->generation < gen_cutoff) {
+				t = (*next)->item->generation;
+				if (t < p_gen_cutoff)
+					p_gen_cutoff = t;
+			}
+
+			next = &(*next)->next;
+			continue;
+		}
+
+		skel_walk_step(revs, next);
+	}
+
+	/*
+	 * Double back to get the parents of commits above gen_cutoff.
+	 */
+	next = &skel->walk;
+	while (*next) {
+		if ((*next)->item->generation < p_gen_cutoff) {
+			next = &(*next)->next;
+			continue;
+		}
+
+		skel_walk_step(revs, next);
+	}
 }

 static void reset_topo_walk(struct rev_info *revs)
@@ -3375,6 +3560,12 @@ static void init_topo_walk(struct rev_info *revs)
 {
 	struct topo_walk_info *info;
 	struct commit_list *list;
+	struct skel_walk_list **tail = NULL;
+	struct skel_info *skel = NULL;
+
+	if (revs->ignore_merge_bases)
+		skel = revs->skel_info;
+
 	if (revs->topo_walk_info)
 		reset_topo_walk(revs);

@@ -3387,6 +3578,13 @@ static void init_topo_walk(struct rev_info *revs)
 	memset(&info->indegree_queue, 0, sizeof(info->indegree_queue));
 	memset(&info->topo_queue, 0, sizeof(info->topo_queue));

+	if (skel) {
+		tail = &skel->walk;
+		*tail = NULL;
+		skel->next_comp = 1;
+	}
+
+
 	switch (revs->sort_order) {
 	default: /* REV_SORT_IN_GRAPH_ORDER */
 		info->topo_queue.compare = NULL;
@@ -3411,16 +3609,23 @@ static void init_topo_walk(struct rev_info *revs)
 		if (parse_commit_gently(c, 1))
 			continue;

-		test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);
-		test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);
-
 		if (c->generation < info->min_generation)
 			info->min_generation = c->generation;

-		*(indegree_slab_at(&info->indegree, c)) = 1;
+		test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);

 		if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE)
 			record_author_date(&info->author_date, c);
+
+		*(indegree_slab_at(&info->indegree, c)) = 1;
+
+		if (skel) {
+			tail = swl_append(c, NULL, tail);
+			continue;
+		}
+
+		test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);
+
 	}
 	compute_indegrees_to_depth(revs, info->min_generation);

@@ -3457,6 +3662,11 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
 {
 	struct commit_list *p;
 	struct topo_walk_info *info = revs->topo_walk_info;
+	struct skel_info *skel = revs->skel_info;
+
+	if (!revs->ignore_merge_bases)
+		skel = NULL;
+
 	if (process_parents(revs, commit, NULL, NULL) < 0) {
 		if (!revs->ignore_missing_links)
 			die("Failed to traverse parents of commit %s",
@@ -3480,9 +3690,11 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)

 		pi = indegree_slab_at(&info->indegree, parent);

-		(*pi)--;
-		if (*pi == 1)
-			prio_queue_put(&info->topo_queue, parent);
+		if (!skel ||
+		    (skel_slab_at(&skel->slab, parent)->component != skel_slab_at(&skel->slab, commit)->component ||
+		     skel_slab_at(&skel->slab, parent)->child == commit ))
+			if (--(*pi) == 1)
+				prio_queue_put(&info->topo_queue, parent);

 		if (revs->first_parent_only)
 			return;
@@ -3531,7 +3743,9 @@ int prepare_revision_walk(struct rev_info *revs)
 		if (limit_list(revs) < 0)
 			return -1;
 		if (revs->topo_order)
-			sort_in_topological_order(&revs->commits, revs->sort_order);
+			sort_in_topological_order(&revs->commits,
+						  revs->skel_info,
+						  revs->sort_order);
 	} else if (revs->topo_order)
 		init_topo_walk(revs);
 	if (revs->line_level_traverse)
@@ -3987,11 +4201,13 @@ static void create_boundary_commit_list(struct rev_info *revs)
 		commit_list_insert(c, &revs->commits);
 	}

+	revs->ignore_merge_bases = 0;
+
 	/*
 	 * If revs->topo_order is set, sort the boundary commits
 	 * in topological order
 	 */
-	sort_in_topological_order(&revs->commits, revs->sort_order);
+	sort_in_topological_order(&revs->commits, NULL, revs->sort_order);
 }

 static struct commit *get_revision_internal(struct rev_info *revs)
diff --git a/revision.h b/revision.h
index 93491b79d4..b33fbe8829 100644
--- a/revision.h
+++ b/revision.h
@@ -88,6 +88,21 @@ struct rev_cmdline_info {
 struct oidset;
 struct topo_walk_info;

+struct skel_datum {
+	int component;
+	struct commit *child;
+};
+
+define_shared_commit_slab(skel_slab, struct skel_datum);
+
+struct skel_walk_list;
+
+struct skel_info {
+	struct skel_walk_list *walk;
+	int next_comp;
+	struct skel_slab slab;
+};
+
 struct rev_info {
 	/* Starting list */
 	struct commit_list *commits;
@@ -137,6 +152,7 @@ struct rev_info {
 			show_pulls:1,
 			topo_order:1,
 			simplify_merges:1,
+			ignore_merge_bases:1,
 			simplify_by_decoration:1,
 			single_worktree:1,
 			tag_objects:1,
@@ -307,6 +323,7 @@ struct rev_info {
 	 * This is loaded from the commit-graph being used.
 	 */
 	struct bloom_filter_settings *bloom_filter_settings;
+	struct skel_info *skel_info;
 };

 int ref_excluded(struct string_list *, const char *path);
-- 
2.27.0

[PATCH 3/3] Add new tests of --ignore-merge-bases

[Antonio Russo]

Extend t4215 and t6016 to also use --ignore-merge-bases on their test
cases.

Add the new test case t4217-log-merges, with three tests: a standard
feature merge, a "twisted" feature merge, and the motivating case for
ignore-merge-bases: a "mountain" of merges.

Signed-off-by: Antonio Russo <antonio.e.russo@gmail.com>
---
 t/t4215-log-skewed-merges.sh               | 169 +++++++++++++
 t/t4217-log-merges.sh                      | 273 +++++++++++++++++++++
 t/t6016-rev-list-graph-simplify-history.sh |  70 ++++++
 3 files changed, 512 insertions(+)
 create mode 100755 t/t4217-log-merges.sh

diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 28d0779a8c..6baefef5e3 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -38,6 +38,22 @@ test_expect_success 'log --graph with merge fusing with its left and right neigh
 	EOF
 '

+test_expect_success 'log --graph with merge fusing with its left and right neighbors (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases <<-\EOF
+	*   H
+	|\
+	| *   G
+	| |\
+	| | * F
+	| *   E
+	| |\
+	| | * D
+	| * C
+	* B
+	* A
+	EOF
+'
+
 test_expect_success 'log --graph with left-skewed merge' '
 	git checkout --orphan 0_p && test_commit 0_A &&
 	git checkout -b 0_q 0_p && test_commit 0_B &&
@@ -72,6 +88,20 @@ test_expect_success 'log --graph with left-skewed merge' '
 	EOF
 '

+test_expect_success 'log --graph with left-skewed merge (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases <<-\EOF
+	*-----.   0_H
+	|\ \ \ \
+	| | | | * 0_G
+	| | | * 0_F
+	| | | * 0_E
+	| | * 0_D
+	| | * 0_C
+	| * 0_B
+	* 0_A
+	EOF
+'
+
 test_expect_success 'log --graph with nested left-skewed merge' '
 	git checkout --orphan 1_p &&
 	test_commit 1_A &&
@@ -100,6 +130,21 @@ test_expect_success 'log --graph with nested left-skewed merge' '
 	EOF
 '

+test_expect_success 'log --graph with nested left-skewed merge (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases<<-\EOF
+	*   1_H
+	|\
+	| *   1_G
+	| |\
+	| | * 1_F
+	| * 1_E
+	| * 1_D
+	* 1_C
+	* 1_B
+	* 1_A
+	EOF
+'
+
 test_expect_success 'log --graph with nested left-skewed merge following normal merge' '
 	git checkout --orphan 2_p &&
 	test_commit 2_A &&
@@ -137,6 +182,23 @@ test_expect_success 'log --graph with nested left-skewed merge following normal
 	EOF
 '

+test_expect_success 'log --graph with nested left-skewed merge following normal merge (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases<<-\EOF
+	*   2_K
+	|\
+	| *   2_J
+	| |\
+	| | * 2_H
+	| | * 2_G
+	| | * 2_F
+	| * 2_E
+	| * 2_D
+	* 2_C
+	* 2_B
+	* 2_A
+	EOF
+'
+
 test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge' '
 	git checkout --orphan 3_p &&
 	test_commit 3_A &&
@@ -170,6 +232,23 @@ test_expect_success 'log --graph with nested right-skewed merge following left-s
 	EOF
 '

+test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases<<-\EOF
+	*   3_J
+	|\
+	| *   3_H
+	| |\
+	| | * 3_G
+	| * 3_F
+	| *   3_E
+	| |\
+	| | * 3_D
+	| * 3_C
+	| * 3_B
+	* 3_A
+	EOF
+'
+
 test_expect_success 'log --graph with right-skewed merge following a left-skewed one' '
 	git checkout --orphan 4_p &&
 	test_commit 4_A &&
@@ -202,6 +281,23 @@ test_expect_success 'log --graph with right-skewed merge following a left-skewed
 	EOF
 '

+test_expect_success 'log --graph with right-skewed merge following a left-skewed one (ignore-merge-bases)' '
+	check_graph --date-order --ignore-merge-bases<<-\EOF
+	*   4_H
+	|\
+	| *   4_G
+	| |\
+	| * | 4_F
+	| * |   4_E
+	| |\ \
+	| | * | 4_D
+	| |  /
+	| | * 4_C
+	| * 4_B
+	* 4_A
+	EOF
+'
+
 test_expect_success 'log --graph with octopus merge with column joining its penultimate parent' '
 	git checkout --orphan 5_p &&
 	test_commit 5_A &&
@@ -239,6 +335,21 @@ test_expect_success 'log --graph with octopus merge with column joining its penu
 	EOF
 '

+test_expect_success 'log --graph with octopus merge with column joining its penultimate parent (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases<<-\EOF
+	*   5_H
+	|\
+	| *-.   5_G
+	| |\ \
+	| | | * 5_F
+	| | * 5_E
+	| | * 5_C
+	| * 5_B
+	* 5_D
+	* 5_A
+	EOF
+'
+
 test_expect_success 'log --graph with multiple tips' '
 	git checkout --orphan 6_1 &&
 	test_commit 6_A &&
@@ -281,6 +392,29 @@ test_expect_success 'log --graph with multiple tips' '
 	EOF
 '

+test_expect_success 'log --graph with multiple tips (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases 6_1 6_3 6_5 <<-\EOF
+	*   6_I
+	|\
+	| | *   6_H
+	| | |\
+	| | | * 6_G
+	| | * | 6_E
+	| | | | * 6_F
+	| |_|_|/|
+	|/| | |/
+	| | |/|
+	| |/| |
+	| * | | 6_D
+	|  / /
+	* / / 6_C
+	|/ /
+	* / 6_B
+	|/
+	* 6_A
+	EOF
+'
+
 test_expect_success 'log --graph with multiple tips and colors' '
 	test_config log.graphColors red,green,yellow,blue,magenta,cyan &&
 	cat >expect.colors <<-\EOF &&
@@ -370,4 +504,39 @@ test_expect_success 'log --graph with multiple tips' '
 	EOF
 '

+test_expect_success 'log --graph with multiple tips (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases M_1 M_3 M_5 M_7 <<-\EOF
+	*   7_M1
+	|\
+	| | *   7_M2
+	| | |\
+	| | | * 7_H
+	| | | | *   7_M3
+	| | | | |\
+	| | | | | * 7_J
+	| | | | * | 7_I
+	| | | | | | *   7_M4
+	| |_|_|_|_|/|\
+	|/| | | | |/ /
+	| | |_|_|/| /
+	| |/| | | |/
+	| | | |_|/|
+	| | |/| | |
+	| | * | | | 7_G
+	| | | |_|/
+	| | |/| |
+	| | * | | 7_F
+	| * | | | 7_E
+	| | |/ /
+	| |/| |
+	| * | | 7_D
+	|  / /
+	* / / 7_C
+	|/ /
+	* / 7_B
+	|/
+	* 7_A
+	EOF
+'
+
 test_done
diff --git a/t/t4217-log-merges.sh b/t/t4217-log-merges.sh
new file mode 100755
index 0000000000..84b1973131
--- /dev/null
+++ b/t/t4217-log-merges.sh
@@ -0,0 +1,273 @@
+#!/bin/sh
+
+test_description='git log --graph of merges'
+
+. ./test-lib.sh
+. "$TEST_DIRECTORY"/lib-log-graph.sh
+
+check_graph () {
+	cat >expect &&
+	lib_test_cmp_graph --format=%s "$@"
+}
+
+test_expect_success 'log --graph with merge pulling in a feature' '
+	git checkout --orphan _p && test_commit A &&
+	git checkout -b _q &&
+	git checkout _p && test_commit B &&
+	git checkout -b _r &&
+	git checkout _p && test_commit C &&
+	git checkout _r && test_commit F_1 &&
+	git checkout _q && test_commit F_2 &&
+	git checkout _r && git merge --no-ff _q -m M &&
+	git checkout _p && git merge --no-ff _r -m D &&
+
+	check_graph <<-\EOF
+	*   D
+	|\
+	| *   M
+	| |\
+	| | * F_2
+	| * | F_1
+	* | | C
+	|/ /
+	* / B
+	|/
+	* A
+	EOF
+'
+
+test_expect_success 'log --graph with merge pulling in a feature (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases <<-\EOF
+	*   D
+	|\
+	| *   M
+	| |\
+	| | * F_2
+	| * F_1
+	* C
+	* B
+	* A
+	EOF
+'
+
+test_expect_success 'log --graph with twisted merge pulling in a feature from master' '
+	git checkout --orphan 0_p && test_commit 0_A &&
+	git checkout -b 0_q &&
+	git checkout 0_p && test_commit 0_B &&
+	git checkout -b 0_r &&
+	git checkout 0_p && test_commit 0_C &&
+	git checkout 0_q && test_commit 0_F1 && git merge --no-ff 0_r -m 0_M1 &&
+	git checkout 0_p && git merge --no-ff 0_q -m 0_M2 &&
+
+	check_graph <<-\EOF
+	*   0_M2
+	|\
+	| *   0_M1
+	| |\
+	| * | 0_F1
+	* | | 0_C
+	| |/
+	|/|
+	* | 0_B
+	|/
+	* 0_A
+	EOF
+'
+
+test_expect_success 'log --graph with twisted merge pulling in a feature from master (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases <<-\EOF
+	*   0_M2
+	|\
+	| * 0_M1
+	| * 0_F1
+	* 0_C
+	* 0_B
+	* 0_A
+	EOF
+'
+
+test_expect_success 'log --graph with several merges' '
+	git checkout --orphan 1_p &&
+	test_commit 1_root &&
+	for m in $(test_seq 1 10) ;
+	do
+		git checkout -b 1_f${m} 1_root ;
+		test_commit 1_A${m} ;
+	done &&
+	for m in $(test_seq 1 10) ;
+	do
+		i=$((11 - $m)) ;
+		git merge --no-ff 1_f${i} -m 1_M${m}A${i} ;
+	done &&
+	for mp in $(test_seq 1 10) ;
+	do
+		m=$((11 - mp))
+		git checkout 1_f${m} ;
+		test_commit 1_B${m} ;
+		git checkout 1_p ;
+		git merge --no-ff 1_f${m} -m 1_M${m} ;
+	done &&
+
+	check_graph <<-\EOF
+	*   1_M1
+	|\
+	| * 1_B1
+	* |   1_M2
+	|\ \
+	| * | 1_B2
+	* | |   1_M3
+	|\ \ \
+	| * | | 1_B3
+	* | | |   1_M4
+	|\ \ \ \
+	| * | | | 1_B4
+	* | | | |   1_M5
+	|\ \ \ \ \
+	| * | | | | 1_B5
+	* | | | | |   1_M6
+	|\ \ \ \ \ \
+	| * | | | | | 1_B6
+	* | | | | | |   1_M7
+	|\ \ \ \ \ \ \
+	| * | | | | | | 1_B7
+	* | | | | | | |   1_M8
+	|\ \ \ \ \ \ \ \
+	| * | | | | | | | 1_B8
+	* | | | | | | | |   1_M9
+	|\ \ \ \ \ \ \ \ \
+	| * | | | | | | | | 1_B9
+	* | | | | | | | | |   1_M10
+	|\ \ \ \ \ \ \ \ \ \
+	| * | | | | | | | | | 1_B10
+	| * | | | | | | | | |   1_M10A1
+	| |\ \ \ \ \ \ \ \ \ \
+	| | | |_|_|_|_|_|_|_|/
+	| | |/| | | | | | | |
+	| | * | | | | | | | | 1_A1
+	| |/ / / / / / / / /
+	|/| | | | | | | | |
+	| * | | | | | | | |   1_M9A2
+	| |\ \ \ \ \ \ \ \ \
+	| | | |_|_|_|_|_|_|/
+	| | |/| | | | | | |
+	| | * | | | | | | | 1_A2
+	| |/ / / / / / / /
+	|/| | | | | | | |
+	| * | | | | | | |   1_M8A3
+	| |\ \ \ \ \ \ \ \
+	| | | |_|_|_|_|_|/
+	| | |/| | | | | |
+	| | * | | | | | | 1_A3
+	| |/ / / / / / /
+	|/| | | | | | |
+	| * | | | | | |   1_M7A4
+	| |\ \ \ \ \ \ \
+	| | | |_|_|_|_|/
+	| | |/| | | | |
+	| | * | | | | | 1_A4
+	| |/ / / / / /
+	|/| | | | | |
+	| * | | | | |   1_M6A5
+	| |\ \ \ \ \ \
+	| | | |_|_|_|/
+	| | |/| | | |
+	| | * | | | | 1_A5
+	| |/ / / / /
+	|/| | | | |
+	| * | | | |   1_M5A6
+	| |\ \ \ \ \
+	| | | |_|_|/
+	| | |/| | |
+	| | * | | | 1_A6
+	| |/ / / /
+	|/| | | |
+	| * | | |   1_M4A7
+	| |\ \ \ \
+	| | | |_|/
+	| | |/| |
+	| | * | | 1_A7
+	| |/ / /
+	|/| | |
+	| * | |   1_M3A8
+	| |\ \ \
+	| | | |/
+	| | |/|
+	| | * | 1_A8
+	| |/ /
+	|/| |
+	| * | 1_M2A9
+	| |\|
+	| | * 1_A9
+	| |/
+	|/|
+	| * 1_A10
+	|/
+	* 1_root
+	EOF
+'
+
+test_expect_success 'log --graph with several merges (ignore-merge-bases)' '
+	check_graph --ignore-merge-bases <<-\EOF
+	*   1_M1
+	|\
+	| * 1_B1
+	*   1_M2
+	|\
+	| * 1_B2
+	*   1_M3
+	|\
+	| * 1_B3
+	*   1_M4
+	|\
+	| * 1_B4
+	*   1_M5
+	|\
+	| * 1_B5
+	*   1_M6
+	|\
+	| * 1_B6
+	*   1_M7
+	|\
+	| * 1_B7
+	*   1_M8
+	|\
+	| * 1_B8
+	*   1_M9
+	|\
+	| * 1_B9
+	*   1_M10
+	|\
+	| * 1_B10
+	| *   1_M10A1
+	| |\
+	| | * 1_A1
+	| *   1_M9A2
+	| |\
+	| | * 1_A2
+	| *   1_M8A3
+	| |\
+	| | * 1_A3
+	| *   1_M7A4
+	| |\
+	| | * 1_A4
+	| *   1_M6A5
+	| |\
+	| | * 1_A5
+	| *   1_M5A6
+	| |\
+	| | * 1_A6
+	| *   1_M4A7
+	| |\
+	| | * 1_A7
+	| *   1_M3A8
+	| |\
+	| | * 1_A8
+	| *   1_M2A9
+	| |\
+	| | * 1_A9
+	| * 1_A10
+	* 1_root
+	EOF
+'
+
+test_done
diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh
index b6b2ab33ab..2217e78fcd 100755
--- a/t/t6016-rev-list-graph-simplify-history.sh
+++ b/t/t6016-rev-list-graph-simplify-history.sh
@@ -79,6 +79,27 @@ test_expect_success '--graph --all' '
 	EOF
 '

+# Make sure that ignore_merge_bases produces a spanning tree
+test_expect_success '--graph --ignore-merge-bases --all' '
+	check_graph --ignore-merge-bases --all <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	| * C3
+	* A5
+	*-.   A4
+	|\ \
+	| | * C2
+	| | * C1
+	| * B2
+	| * B1
+	* A3
+	* A2
+	* A1
+	EOF
+'
+
 # 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' '
@@ -148,6 +169,19 @@ test_expect_success '--graph --full-history -- bar.txt' '
 	EOF
 '

+test_expect_success '--graph --ignore-merge-bases --full-history -- bar.txt' '
+	check_graph --ignore-merge-bases --full-history --all -- bar.txt <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	* A5
+	* A4
+	* A3
+	* A2
+	EOF
+'
+
 test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '
 	check_graph --full-history --simplify-merges --all -- bar.txt <<-\EOF
 	* A7
@@ -161,6 +195,18 @@ test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '
 	EOF
 '

+test_expect_success '--graph --ignore-merge-bases --full-history --simplify-merges -- bar.txt' '
+	check_graph --ignore-merge-bases --full-history --simplify-merges --all -- bar.txt <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	* A5
+	* A3
+	* A2
+	EOF
+'
+
 test_expect_success '--graph -- bar.txt' '
 	check_graph --all -- bar.txt <<-\EOF
 	* A7
@@ -244,4 +290,28 @@ test_expect_success '--graph --boundary ^C3' '
 	EOF
 '

+test_expect_success '--graph --ignore-merge-bases --boundary ^C3' '
+	check_graph --ignore-merge-bases --boundary --all ^C3 <<-\EOF
+	* A7
+	*   A6
+	|\
+	| * C4
+	* | A5
+	| |
+	|  \
+	*-. \   A4
+	|\ \ \
+	| * | | B2
+	| * | | B1
+	* | | | A3
+	o | | | A2
+	|/ / /
+	o / / A1
+	 / /
+	| o C3
+	|/
+	o C2
+	EOF
+'
+
 test_done
-- 
2.27.0

Re: [PATCH 1/3] Clean up t6016-rev-list-graph-simplify-history

[Junio C Hamano]

Antonio Russo <antonio.e.russo@gmail.com> writes:

> Subject: Re: [PATCH 1/3] Clean up t6016-rev-list-graph-simplify-history

Hmph, didn't anybody give you guidance on the subjects the last
round?

If this is a second round (I do not recall---I read too many
patches), the subject should begin with

	[PATCH v2 1/3]

and then "<area>: one line summary".  For test scripts, the script
number is enough to identify the area the patch affects, e.g.

	[PATCH v2 1/3] t6016: simplify the way expected history is drawn

> Simplifies the logic used to test rev-list, making adding new tests
> easier.  Uses a heredoc and sed expansion of the expected output,
> instead of shell substitutions and manually escaped echo's.

Justify why this change is a good thing upfront, by (1) giving a
short summary of what is done in the current code and (2) saying
what is suboptimal in it.

    Many tests in this script prepare each line of the expected
    --graph output separately with "echo", using bare object names
    of commits shown in the graph (captured in shell variables), run
    "rev-list --graph" with some other parameters and compares the
    result.  The expected shape of the graph is hard to see and the
    resulting code is repetitious.

And then outline your solution, giving orders to the codebase to
"become like so", in the next paragraph.

    In order to add new tests easier, introduce a helper function
    that takes extra parameters given to the "rev-list --graph" as
    its arguments, and the expected output from its standard input
    stream.  By allowing tagnames to be used in the expected output,
    eliminate the need to capture commit object names in shell
    variables.

cf. Documentation/SubmittingPatches::imperative-mood

> Reviewed-by: Junio C Hamano <gitster@pobox.com>

I didn't review this version (in other words, I think you changed
the patch after I reviewed)---so do not write this line.  It is
misleading.

>  . ./test-lib.sh
>
> +check_graph () {
> +	sed -f expand_tag_to_oid.sed >expect &&
> +	git rev-list --graph "$@" >actual &&
> +	sed 's/ *$//' actual >actual.sanitized &&
> +	test_cmp expect actual.sanitized
> +}

OK, so we prepare the mapping from tagname to objectname somewhere,
feed an expected output that uses tagname to this helper function
and munge it into the file expect, and then compare it with the
actual output.  

Why do we drop the trailing whitespace in the output before
comparing?  Is it because it does not matter?  Is it because it is
cumbersome to spell in the expected output in the source?

Not complaining.  But if we truly aim to make writing new tests
easier, we should tell those who may write new tests what they are
expected to be doing when using this helper function in a comment
before it to help them.  Some points I can think of off the top of
my head are:

 * The file expend_tag_to_oid.sed is created in a single "setup"
   test;  when adding a new test, the shape of the history and new
   tags used in it must be prepared before the "for-each-ref" that
   produces the file in the "setup" test.

 * The arguments to the helper are given to "git rev-list --graph"
   to be compared with the expected graph fed from the standard
   input.

 * The expected graph can use tags and branches instead of object
   names (and it is encouraged to do so) for readability.  You do
   not mimick trailing whitespaces on the lines [*1*].


>  test_expect_success '--graph --all' '
> -	rm -f expected &&
> -	echo "* $A7" >> expected &&
> -	echo "*   $A6" >> expected &&
> -	echo "|\\  " >> expected &&
> -	echo "| * $C4" >> expected &&
> -	echo "| * $C3" >> expected &&
> -	echo "* | $A5" >> expected &&
> -	echo "| |   " >> expected &&
> -	echo "|  \\  " >> expected &&
> -	echo "*-. | $A4" >> expected &&
> -	echo "|\\ \\| " >> expected &&
> -	echo "| | * $C2" >> expected &&
> -	echo "| | * $C1" >> expected &&
> -	echo "| * | $B2" >> expected &&
> -	echo "| * | $B1" >> expected &&
> -	echo "* | | $A3" >> expected &&
> -	echo "| |/  " >> expected &&
> -	echo "|/|   " >> expected &&
> -	echo "* | $A2" >> expected &&
> -	echo "|/  " >> expected &&
> -	echo "* $A1" >> expected &&
> -	git rev-list --graph --all > actual &&
> -	test_cmp expected actual
> -	'
> +	check_graph --all <<-\EOF
> +	* A7
> +	*   A6
> +	|\
> +	| * C4
> +	| * C3
> +	* | A5
> +	| |
> +	|  \
> +	*-. | A4
> +	|\ \|
> +	| | * C2
> +	| | * C1
> +	| * | B2
> +	| * | B1
> +	* | | A3
> +	| |/
> +	|/|
> +	* | A2
> +	|/
> +	* A1
> +	EOF
> +'

I do agree that the resulting test is easier to understand.

Thanks.

[Footnote *1*]

This is a tangent, but I wonder if somebody looked into how feasible
it is to eliminate the trailing whitespace in the graph output.  It
is OK to give whitespaces in anticipation of writing the commit
object names, but on a line in the output that exists only to show
connecting lines, where we know we will not write anything after the
graph, there is no excuse to end the graph part with a trailing
whitespace.