Skip to contentSkip to conversation

Teach git-rev-list --simplify-forks

PATCH Superseded Antonio Russo 5 participants 17 messages Apr 27, 2020 – May 2, 2020 Documentation

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Teach git-rev-list --simplify-forks

When used with --graph, instead of displaying the full graph, display a spanning subgraph produced by a depth-first search of the graph visiting parents from left to right. Edges to already visited commits are discarded. This process is repeated for every commit to be displayed.

This is valuable to reduce visual clutter when there are many merges that were not rebased onto each other and the user is primarily interested in the state of the branch being merged into.

Also adds documentation and tests of the above.

---
 Documentation/rev-list-options.txt         |  8 +++
 revision.c                                 | 67 +++++++++++++++++++++-
 revision.h                                 |  6 ++
 t/t6016-rev-list-graph-simplify-history.sh | 50 ++++++++++++++++
 4 files changed, 130 insertions(+), 1 deletion(-)

Hello,

I'm trying to address a long-standing problem I've had visualizing complex git repositories with git log --graph. I think that a picture is worth a thousand words, so I'll just show what the patch does for git master:

% git log --graph --abbrev-commit --pretty=oneline --simplify-forks e870325ee8

Quoted 24 lines

* e870325ee8 (HEAD -> master, origin/master, origin/HEAD) The third batch
* a397e9c236 Merge branch 'jk/credential-parsing-end-of-host-in-URL'
|\
| * 4c5971e18a credential: treat "?" and "#" in URLs as end of host
* d6d561db1c Merge branch 'jt/rebase-allow-duplicate'
|\
| * 0fcb4f6b62 rebase --merge: optionally skip upstreamed commits
* c7d8f69da5 Merge branch 'en/rebase-no-keep-empty'

|\
| * 50ed76148a rebase: fix an incompatible-options error message
| * b9cbd2958f rebase: reinstate --no-keep-empty
| * 1b5735f75c rebase -i: mark commits that begin empty in todo editor
*   8b39dfdf47 Merge branch 'js/mingw-is-hidden-test-fix'
|\
| * 176a66a748 t: restrict `is_hidden` to be called only on Windows
| * 9814d0a4ad mingw: make test_path_is_hidden more robust
| * 7c2dfca7e8 t: consolidate the `is_hidden` functions

* a41b41ca74 Merge branch 'js/mingw-isilon-nfs'
|\
| * 23eafd924a mingw: cope with the Isilon network file system
* 33feaca6bf Merge branch 'js/flush-prompt-before-interative-input'

|\
| * 1f09aed834 interactive: explicitly `fflush` stdout before expecting input
| * 08d383f23e interactive: refactor code asking the user for interactive input
Quoted 7 lines

* 9af3a7cb4d Merge branch 'ds/revision-show-pulls'
|\
| * 8d049e182e revision: --show-pulls adds helpful merges
* 82fa169d55 Merge branch 'ma/simplify-merge-config-parsing'
|\
| * 9881b451f3 merge: use skip_prefix to parse config key
* b3eb70e0f8 Merge branch 'js/mingw-fixes'

Compare this to before:

% git log --graph --abbrev-commit --pretty=oneline e870325ee8

Quoted 28 lines

* e870325ee8 (HEAD -> master, origin/master, origin/HEAD) The third batch
* a397e9c236 Merge branch 'jk/credential-parsing-end-of-host-in-URL'
|\
| * 4c5971e18a credential: treat "?" and "#" in URLs as end of host
* | d6d561db1c Merge branch 'jt/rebase-allow-duplicate'
|\ \

| * | 0fcb4f6b62 rebase --merge: optionally skip upstreamed commits
* | | c7d8f69da5 Merge branch 'en/rebase-no-keep-empty'
|\| |
| * | 50ed76148a rebase: fix an incompatible-options error message
| * | b9cbd2958f rebase: reinstate --no-keep-empty
| * | 1b5735f75c rebase -i: mark commits that begin empty in todo editor
* | |   8b39dfdf47 Merge branch 'js/mingw-is-hidden-test-fix'
|\ \ \
| * | | 176a66a748 t: restrict `is_hidden` to be called only on Windows
| * | | 9814d0a4ad mingw: make test_path_is_hidden more robust
| * | | 7c2dfca7e8 t: consolidate the `is_hidden` functions
* | | |   a41b41ca74 Merge branch 'js/mingw-isilon-nfs'
|\ \ \ \
| * | | | 23eafd924a mingw: cope with the Isilon network file system
| |/ / /
* | | |   33feaca6bf Merge branch 'js/flush-prompt-before-interative-input'
|\ \ \ \
| * | | | 1f09aed834 interactive: explicitly `fflush` stdout before expecting input
| * | | | 08d383f23e interactive: refactor code asking the user for interactive input
| |/ / /
* | | |   9af3a7cb4d Merge branch 'ds/revision-show-pulls'
|\ \ \ \
Quoted 8 lines
| * | | | 8d049e182e revision: --show-pulls adds helpful merges
| |/ / /
* | | |   82fa169d55 Merge branch 'ma/simplify-merge-config-parsing'
|\ \ \ \
| * | | | 9881b451f3 merge: use skip_prefix to parse config key
| |/ / /
* | | |   b3eb70e0f8 Merge branch 'js/mingw-fixes'
|\ \ \ \

Roughly, the tool produces a spanning tree by traversing the commit graph, leftmost parents first. It forgets information about where forks occurred, removing the "tails" that connect branches back to their original fork point. These "tails" can be very long and often do not contain information that is very important for someone glancing through commits.

=== Details

It's about 40% faster. Tested this on current master (of git):

git log --graph --pretty=oneline --simplify-forks e870325ee8 > /dev/null 0.83s user 0.06s system 99% cpu 0.886 total

git log --graph --pretty=oneline e870325ee8 > /dev/null 1.41s user 0.03s system 99% cpu 1.443 total

This is because the produced graph is much simpler---it is a tree in the above case (though not in general).

The exact approach uses two flags (reusing bits 27 and 28 that are used by the topological sort walk). One says whether the commit has been ever visited, and the other says whether the commit was visited from the current root. The walk does not continue down any commit that was visited, and leaves the connection to the parent only if has not been visited from the current root. Each commit that is to be shown is treated as its own root (most of these root commits are immediately skipped, because they are likely visited in an earlier traversal).

=== Problems

Travis CI is showing issues with the tests I've added [1]. I cannot reproduce them locally, neither with gcc 4.8.5 (RHEL) nor 9.3.0 (Debian). They're also only failing on one of the runners.

Thank you for taking the time to look at this,
Antonio Russo

[1] https://travis-ci.org/github/aerusso/git
[2] https://github.com/aerusso/git/tree/mrs/simplify-history-forks

Documentation/rev-list-options.txt +8 -0
index 04ad7dd36e..cbac09028c 100644
@@ -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
revision.c +66 -1

88 lines not on this page · raw message

revision.h +6 -0
index c1af164b30..f1abdb26b0 100644
@@ -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,
t/t6016-rev-list-graph-simplify-history.sh +50 -0

68 lines not on this page · raw message

Signature · 1 line
2.26.2
#1 lore raw
Quoted 5 lines · Antonio Russo

=== Problems

Travis CI is showing issues with the tests I've added [1]. I cannot reproduce them locally, neither with gcc 4.8.5 (RHEL) nor 9.3.0 (Debian). They're also only failing on one of the runners.

This is probably because the tests run a second round with GIT_TEST_COMMIT_GRAPH=1, which enables the commit-graph feature. This triggers a different set of logic for the topo-order, which ignores the logic the way you inserted it here.

Thanks,
-Stolee

#2 lore raw
Quoted 3 lines · Derrick Stolee

This is probably because the tests run a second round with GIT_TEST_COMMIT_GRAPH=1, which enables the commit-graph feature. This triggers a different set of logic for the topo-order, which ignores the logic the way you inserted it here.

Thank you for pointing me at this. If I now understand correctly, the commit information is not yet necessarily loaded for all commits at this point, and therefore the logic here will need to be called later on (and makes it more complicated).

Am I correct that this loading of parents happens during traverse_commit_list_filtered (for the case of rev-list)? Also, am I correct that there are not yet any hooks to filter out edges (of the graph of commits)?

Thank you,
Antonio

#3 lore raw
Quoted 5 lines · Antonio Russo
Quoted 3 lines · Derrick Stolee

This is probably because the tests run a second round with GIT_TEST_COMMIT_GRAPH=1, which enables the commit-graph feature. This triggers a different set of logic for the topo-order, which ignores the logic the way you inserted it here.

Quoted 7 lines

Thank you for pointing me at this. If I now understand correctly, the commit information is not yet necessarily loaded for all commits at this point, and therefore the logic here will need to be called later on (and makes it more complicated).

Am I correct that this loading of parents happens during traverse_commit_list_filtered (for the case of rev-list)? Also, am I correct that there are not yet any hooks to filter out edges (of the graph of commits)?

I mean that if you have a commit-graph, then a completely disjoint set of code is run instead of the code you modified. See [1] for the blocks of code that are run instead.

[1] https://github.com/git/git/commit/b45424181e9e8b2284a48c6db7b8db635bbfccc8

Thanks,
-Stolee

#4 lore raw

PATCH v2 1/1 Teach git-rev-list --simplify-forks

In reply to Antonio Russo

When used with --graph, instead of displaying the full graph, display a spanning subgraph produced by a depth-first search of the graph visiting parents from left to right. Edges to already visited commits are discarded. This process is repeated for every commit to be displayed.

This is valuable to reduce visual clutter when there are many merges that were not rebased onto each other and the user is primarily interested in the state of the branch being merged into.

Also adds documentation and tests of the above.

---
 Documentation/rev-list-options.txt         |  8 +++
 revision.c                                 | 62 ++++++++++++++++++++++
 revision.h                                 |  6 +++
 t/t6016-rev-list-graph-simplify-history.sh | 50 +++++++++++++++++
 4 files changed, 126 insertions(+)

Hello,

This second revision of the patch sets revs->limited. This forces the graph of commits to be loaded, and simplfiy_forks() therefore reliably traverses it. This addresses the test failures mentioned before (see [1]).

Antonio

[1] https://travis-ci.org/github/aerusso/git/builds/680894920

Documentation/rev-list-options.txt +8 -0
index 04ad7dd36e..cbac09028c 100644
@@ -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
revision.c +62 -0

80 lines not on this page · raw message

revision.h +6 -0
index c1af164b30..f1abdb26b0 100644
@@ -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,
t/t6016-rev-list-graph-simplify-history.sh +50 -0

68 lines not on this page · raw message

Signature · 1 line
2.26.2
#5 lore raw

Hi Antonio,

Quoted 34 lines · Antonio Russo

When used with --graph, instead of displaying the full graph, display a spanning subgraph produced by a depth-first search of the graph visiting parents from left to right. Edges to already visited commits are discarded. This process is repeated for every commit to be displayed.

This is valuable to reduce visual clutter when there are many merges that were not rebased onto each other and the user is primarily interested in the state of the branch being merged into.

Also adds documentation and tests of the above.

---
 Documentation/rev-list-options.txt         |  8 +++
 revision.c                                 | 62 ++++++++++++++++++++++
 revision.h                                 |  6 +++
 t/t6016-rev-list-graph-simplify-history.sh | 50 +++++++++++++++++
 4 files changed, 126 insertions(+)

Hello,

This second revision of the patch sets revs->limited. This forces the graph of commits to be loaded, and simplfiy_forks() therefore reliably traverses it. This addresses the test failures mentioned before (see [1]).

Antonio

[1] https://travis-ci.org/github/aerusso/git/builds/680894920

Documentation/rev-list-options.txt +0 -0
index 04ad7dd36e..cbac09028c 100644

Documentation/rev-list-options.txt Default mode:: · line 372

Quoted 10 lines
Documentation/rev-list-options.txt +7 -0
@@ -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.

Does this also need to actually mention that it effectively discard edges to fork points, as per the option name?. No rebasing required for it to be useful.
     s/when/where/
    "...and not where the branch was last rebased or forked from." - not great but actually mentions the option.

--
Philip

Quoted 190 lines
Documentation/rev-list-options.txt +1 -0
+
 --ancestry-path::
 	When given a range of commits to display (e.g. 'commit1..commit2'
 	or 'commit2 {caret}commit1'), only display commits that exist
revision.c +62 -0
index 5bc96444b6..51dbe21847 100644
@@ -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, "--simplify-forks")) {
+		revs->limited = 1;
+		revs->simplify_forks = 1;
 	} else if (!strcmp(arg, "--date-order")) {
 		revs->sort_order = REV_SORT_BY_COMMIT_DATE;
 		revs->topo_order = 1;
@@ -3095,6 +3098,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,6 +3452,8 @@ 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)
revision.h +6 -0
index c1af164b30..f1abdb26b0 100644
@@ -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,
t/t6016-rev-list-graph-simplify-history.sh +50 -0
index f5e6e92f5b..d99214b6df 100755
@@ -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 &&
#6 lore raw
Quoted 15 lines · Philip Oakley

Documentation/rev-list-options.txt Default mode:: · line 372

Quoted 7 lines

+--simplify-forks::

Documentation/rev-list-options.txt +6 -0
+	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.

Does this also need to actually mention that it effectively discard edges to fork points, as per the option name?. No rebasing required for it to be useful.
     s/when/where/
    "...and not where the branch was last rebased or forked from." - not great but actually mentions the option.

Quoted 2 lines

--
Philip

Good point. More generally, my description of the option is not very useful unless you already basically understand what it's doing.

How about:

Quoted 9 lines

--simplify-forks::
Omits the parent relationship of the first commit of merged branches. Effectively discards all information about the fork point of merged branches. It does so by converting 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 most interested in when branches were merged.

Antonio

#7 lore raw
In reply to Antonio Russo
Quoted 8 lines · Antonio Russo

When used with --graph, instead of displaying the full graph, display a spanning subgraph produced by a depth-first search of the graph visiting parents from left to right. Edges to already visited commits are discarded. This process is repeated for every commit to be displayed.

This is valuable to reduce visual clutter when there are many merges that were not rebased onto each other and the user is primarily interested in the state of the branch being merged into.

My earlier comment to recommend how to fix the test failures intended to demonstrate that this area of code requires a bit of precision. I took some time to review this patch, but I find it needs some significant updates.

tl;dr: The way you manipulate the commit parents seems incorrect to me, but perhaps there is enough prior art in the way we simplify parents to make that acceptable. Someone else will need to chime in on that part.

It may be possible to do this "drop edges" entirely inside of graph.c (the graph rendering code) instead of revision.c, which would automatically work with the performance gains from the newer topo-walk algorithm.

There are enough deviations from code and test style that this will need a significant revision regardless.

Quoted 3 lines

This second revision of the patch sets revs->limited. This forces the graph of commits to be loaded, and simplfiy_forks() therefore reliably traverses it. This addresses the test failures mentioned before (see [1]).

This will have a significant performance impact on the option, as you will not see even the first result until the DFS has completed.

Quoted 5 lines
Documentation/rev-list-options.txt +0 -0
index 04ad7dd36e..cbac09028c 100644

Documentation/rev-list-options.txt Default mode:: · line 372

Quoted 10 lines
Documentation/rev-list-options.txt +7 -0
@@ -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.

Describing the option via the algorithm may not be the best way to inform the user of what they will see. It also will not be informative if the implementation changes to not perform the algorithm described here, because that algorithm is not incremental (it is O(N) where N is the total number of reachable commits, not ~O(n) where n is the number of commits that will actually show up).

An easy test is to time your command with "-n 1".

I'm also not crazy about "when the branch was last rebased". You probably mean "..when you are not interested in which merge base was used for each merge."

Also, this does nothing without "--graph" right? Perhaps it should enable it?

Here is a suggested alternative:

--simplify-forks::
Show commits that are introduced by each merge before showing the first parent of the merge, as in --graph, but remove edges from those commits to commits reachable from the first parent. This helps to visualize repositories with many merges when you are not interested in which merge base was used for each merge. It also reduces the width of the graph visualization compared to --graph.

With this description, perhaps it is worth renaming the option? Perhaps "--ignore-merge-bases"? The word "simplify" implies something like dropping commits from history, but you are instead dropping _edges_ from the graph.

Quoted 8 lines
Documentation/rev-list-options.txt +0 -0
 --ancestry-path::
 	When given a range of commits to display (e.g. 'commit1..commit2'
 	or 'commit2 {caret}commit1'), only display commits that exist
revision.c +0 -0
index 5bc96444b6..51dbe21847 100644

revision.c static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg · line 2087

Quoted 6 lines
revision.c +3 -0
@@ -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, "--simplify-forks")) {
+		revs->limited = 1;
+		revs->simplify_forks = 1;

I recommend dropping the revs->limited setting here and instead fixing the performance instead. But maybe that should be a second patch on top of this one.

revision.c static void simplify_merges(struct rev_info *revs) · line 3104

Quoted 11 lines
revision.c +4 -0
 	} else if (!strcmp(arg, "--date-order")) {
 		revs->sort_order = REV_SORT_BY_COMMIT_DATE;
 		revs->topo_order = 1;
@@ -3095,6 +3098,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;

You want "struct commit_list *parents" here for simpler use.

revision.c static void simplify_merges(struct rev_info *revs) · line 3112

Quoted 8 lines
revision.c +8 -0
+	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) {

This method could use a split into at least two. I count three levels of nested loops here, so please break them up into smaller methods.

revision.c static void simplify_merges(struct rev_info *revs) · line 3116

Quoted 4 lines
revision.c +4 -0
+		/* process every commit to be displayed exactly once */
+		if(iter_list->item->object.flags & SIMP_FORK_VISITED)
+			continue;
+		clear_object_flags(SIMP_FORK_VISITING);

This drops the flag from all commits. This will cause quadratic performance if combined with "--all". Drop this and instead clear the flag yourself as you visit commits.

revision.c static void simplify_merges(struct rev_info *revs) · line 3125

Quoted 9 lines
revision.c +9 -0
+		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) {

You have some whitespace issues. Put a space between "while" and "(". Same with "if"s below.

revision.c static void simplify_merges(struct rev_info *revs) · line 3131

Quoted 6 lines
revision.c +6 -0
+				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);

I don't think you want pop_commit() here. You want to have "parents = parents->next" at the end.

Now, if this is how you are "simplifying" the edges in the final output, then I think this is destructive and unsafe! You are literally modifying "commit->parents" so if another operation in Git tries to read those parents it will see the wrong data.

Think about a different way to achieve your goal here, perhaps in the rendering portion of graph.c instead of here.

revision.c static void simplify_merges(struct rev_info *revs) · line 3143

Quoted 12 lines
revision.c +12 -0
+				} 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);
+				}

It is very unclear that your loop terminates. Instead, use "parents = parents->next" at the end of the loop block to make is extremely clear that the loop behaves as expected.

Of course, this assumes that you are not being destructive to the commit parents as you explore.

revision.c static void simplify_merges(struct rev_info *revs) · line 3148

Quoted 5 lines
revision.c +5 -0
+			}
+
+			/* feed the parents, right to left (reversed) onto the
+			 * stack to do a depth-first traversal of the commit graph
+			 */

nit: multi-line comment style [1]

[1] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L285-L291

revision.c static void simplify_merges(struct rev_info *revs) · line 3151

Quoted 3 lines
revision.c +3 -0
+			while(list_lr) {
+				commit_list_insert(pop_commit(&list_lr), &stack);
+			}

nit: No curly braces around single-line blocks. [2]

[2] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L239-L243

Quoted 23 lines
revision.c +8 -0
+		}
+	}
+
+	clear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING);
+}
+
 static void set_children(struct rev_info *revs)
 {
 	struct commit_list *l;
@@ -3392,6 +3452,8 @@ 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)
revision.h +0 -0
index c1af164b30..f1abdb26b0 100644

revision.h line 57

Quoted 7 lines
revision.h +4 -0
@@ -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)

I don't like that you are re-using these, as it is dangerous for later collisions. At the moment, these flags are not used in the same code paths because you specify "limited = 1" and that code path does not use TOPO_WALK_* macros.

Quoted 27 lines
revision.h +1 -0
 #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,
t/t6016-rev-list-graph-simplify-history.sh +8 -0
index f5e6e92f5b..d99214b6df 100755
@@ -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 &&

t/t6016-rev-list-graph-simplify-history.sh test_expect_success '--graph --all' ' · line 105

Quoted 10 lines
t/t6016-rev-list-graph-simplify-history.sh +10 -0
+	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 &&

Do not use too many echos like this. Instead use t4215-log-skewed-merges.sh as an example [3].

[3] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/t/t4215-log-skewed-merges.sh#L24-L37

I also hope that you can find more complicated cases to test, including:

1. A merge that brings in a merge (think a feature branch)
2. A merge that brings in a twisted merge (think a user using "git pull").

Here are some example --graph and --simplify-forks outputs to try. I have not tested these myself, but I believe they are interesting test cases that can trip up other algorithms.

Merge bringing a merge (non-twisted):

--graph --simplify-forks
* *

 |\		|\
 | *		| *
 | |\		| |\
 | | *		| | *
 | * |		| *
 * | |		*
 |/ /		*

* / *
|/
*

Twisted merge:

--graph --simplify-forks
* *

 |\		|\
 | *		| *
 | |\		| *
 | * |		*
 | | |		*
 * |/		*
 |/|
 * |
 |/

*

Thanks,
-Stolee

#8 lore raw
Quoted 10 lines · Derrick Stolee
Quoted 8 lines · Antonio Russo

When used with --graph, instead of displaying the full graph, display a spanning subgraph produced by a depth-first search of the graph visiting parents from left to right. Edges to already visited commits are discarded. This process is repeated for every commit to be displayed.

This is valuable to reduce visual clutter when there are many merges that were not rebased onto each other and the user is primarily interested in the state of the branch being merged into.

Quoted 8 lines

My earlier comment to recommend how to fix the test failures intended to demonstrate that this area of code requires a bit of precision. I took some time to review this patch, but I find it needs some significant updates.

tl;dr: The way you manipulate the commit parents seems incorrect to me, but perhaps there is enough prior art in the way we simplify parents to make that acceptable. Someone else will need to chime in on that part.

First, thank you for taking the time look at this. I understand your hesitation about the "amputation" of the history, but in some sense that's the point of this option. I really want to be ignorant of the details of when the fork branched off. I would like the reported history to be appear nearly equivalent to a rebase-and-fastforward only merge style, which results in a much simpler git log --graph.

Quoted 3 lines

It may be possible to do this "drop edges" entirely inside of graph.c (the graph rendering code) instead of revision.c, which would automatically work with the performance gains from the newer topo-walk algorithm.

Non-local information about the commit graph needs to be used to do this amputation of the history. We cannot know how many parents we want to display until we've completely explored all the parents of that node. Unfortunately, that means that the whole graph needs to be loaded, and I cannot really see how there would be any gain by doing this in graph.c.

Caveat: there are semi-streaming DFS implementations (i.e., O(n log n) space) that we might be able to use to get the first line out the door quicker. I would, however, like to leave that to another patch.

I will also add that, for the tests I've done, all performance penalties have been insignificant (less than ~5% for showing the first commit), while there are significant performance _improvements_, e.g., ~40% for displaying the full tree.

A notable exception is --all, which can be ~50x faster for the full output, but is often dramatically slower to show anything (i.e., the first line).

Quoted 2 lines

There are enough deviations from code and test style that this will need a significant revision regardless.

(Please see forthcoming revision 3).

Quoted 6 lines
Quoted 3 lines

This second revision of the patch sets revs->limited. This forces the graph of commits to be loaded, and simplfiy_forks() therefore reliably traverses it. This addresses the test failures mentioned before (see [1]).

This will have a significant performance impact on the option, as you will not see even the first result until the DFS has completed.

First of all, short of using some other, more sophisticated streaming version of this algorithm, the full DFS must finish before the first commit having two (or more) parents can be shown.

That said, the performance is not significantly affected:

I ran the following test (2.26.2, with my patch on top of it):
(git lg = git log --graph --pretty=oneline)

% time git lg -n1 --ignore-merge-bases e896a286df > /dev/null 0.73s user 0.02s system 99% cpu 0.746 total

% time git lg -n1 e896a286df > /dev/null
0.72s user 0.01s system 99% cpu 0.731 total

For the linux git repo:

% time git lg -n1 --ignore-merge-bases v5.7-rc3 >/dev/null 9.25s user 0.39s system 99% cpu 9.646 total

% time git lg -n1 v5.7-rc3 >/dev/null
9.02s user 0.35s system 99% cpu 9.378 total

So the performance seems basically unaffected for very limited graphs. It's also about 40% faster for complicated ones (as mentioned in my first email):

% time git lg --ignore-merge-bases e870325ee8 > /dev/null 0.83s user 0.06s system 99% cpu 0.886 total

% time git lg e870325ee8 > /dev/null
1.41s user 0.03s system 99% cpu 1.443 total

For the linux git repo:

% time git lg --ignore-merge-bases v5.7-rc3 >/dev/null 11.86s user 0.62s system 99% cpu 12.489 total

% time git lg v5.7-rc3 >/dev/null
21.56s user 0.55s system 99% cpu 22.108 total

This is because the amputated graph is much simpler, and the rest of the code needs to do much less work.

Passing --all is another beast, and does indeed suffer:

% time git lg --ignore-merge-bases --all >/dev/null 4.06s user 0.04s system 99% cpu 4.105 total

% time git lg --all >/dev/null
189.59s user 0.04s system 99% cpu 3:09.65 total

(and for the first line)

% time git lg -n1 --ignore-merge-bases --all >/dev/null 3.86s user 0.02s system 99% cpu 3.874 total

% time git lg -n1 --all >/dev/null
0.83s user 0.02s system 99% cpu 0.848 total

(If you need to use --all for the Linux git repo, you should not use --ignore-merge-bases).

There's certainly performance improvements to be desired, but they do not appear except for very large repositories, and only when combined with --all.

Quoted 23 lines
Quoted 5 lines
Documentation/rev-list-options.txt +0 -0
index 04ad7dd36e..cbac09028c 100644

Documentation/rev-list-options.txt Default mode:: · line 372

Quoted 10 lines
Documentation/rev-list-options.txt +7 -0
@@ -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.

Describing the option via the algorithm may not be the best way to inform the user of what they will see. It also will not be informative if the implementation changes to not perform the algorithm described here, because that algorithm is not incremental (it is O(N) where N is the total number of reachable commits, not ~O(n) where n is the number of commits that will actually show up).

Quoted 1 line

An easy test is to time your command with "-n 1".

While this is true, it is not the dominant effect (see above).

Quoted 6 lines

I'm also not crazy about "when the branch was last rebased". You probably mean "..when you are not interested in which merge base was used for each merge."

Also, this does nothing without "--graph" right? Perhaps it should enable it?

Not quite. The patch interacts very nicely with gitk!

Quoted 11 lines

Here is a suggested alternative:

--simplify-forks::
Show commits that are introduced by each merge before showing the first parent of the merge, as in --graph, but remove edges from those commits to commits reachable from the first parent. This helps to visualize repositories with many merges when you are not interested in which merge base was used for each merge. It also reduces the width of the graph visualization compared to --graph.

Quoted 4 lines

With this description, perhaps it is worth renaming the option? Perhaps "--ignore-merge-bases"? The word "simplify" implies something like dropping commits from history, but you are instead dropping _edges_ from the graph.

(see revision 3).

Quoted 10 lines
Quoted 10 lines
Documentation/rev-list-options.txt +0 -0
 --ancestry-path::
 	When given a range of commits to display (e.g. 'commit1..commit2'
 	or 'commit2 {caret}commit1'), only display commits that exist
revision.c +0 -0
index 5bc96444b6..51dbe21847 100644
@@ -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;
Quoted 8 lines

revision.c static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg · line 2087

Quoted 4 lines
revision.c +3 -0
 		revs->prune = 1;
+	} else if (!strcmp(arg, "--simplify-forks")) {
+		revs->limited = 1;
+		revs->simplify_forks = 1;

I recommend dropping the revs->limited setting here and instead fixing the performance instead. But maybe that should be a second patch on top of this one.

(See above.)

Quoted 7 lines
Quoted 7 lines
revision.c +0 -0
 	} else if (!strcmp(arg, "--date-order")) {
 		revs->sort_order = REV_SORT_BY_COMMIT_DATE;
 		revs->topo_order = 1;
@@ -3095,6 +3098,63 @@ static void simplify_merges(struct rev_info *revs)
 	}
 }
 
Quoted 6 lines

revision.c static void simplify_merges(struct rev_info *revs) · line 3104

Quoted 4 lines
revision.c +4 -0
+static void simplify_forks(struct rev_info *revs)
+{
+	struct commit_list *stack, *list_lr, *iter_list;
+	struct commit_list **parents;

You want "struct commit_list *parents" here for simpler use.

Using a pointer to the pointer makes the amputation of the parents much more uniform: we can just pop_commit(parents), and it handles the cases of the first parent (which is addressed by commit->parents) and later parents (which are addressed by list_element->next).

Of course, I'm insistent here that we should still be amputating the graph.

Quoted 11 lines

revision.c static void simplify_merges(struct rev_info *revs) · line 3112

Quoted 8 lines
revision.c +8 -0
+	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) {

This method could use a split into at least two. I count three levels of nested loops here, so please break them up into smaller methods.

(see revision 3).

Quoted 8 lines

revision.c static void simplify_merges(struct rev_info *revs) · line 3116

Quoted 4 lines
revision.c +4 -0
+		/* process every commit to be displayed exactly once */
+		if(iter_list->item->object.flags & SIMP_FORK_VISITED)
+			continue;
+		clear_object_flags(SIMP_FORK_VISITING);

This drops the flag from all commits. This will cause quadratic performance if combined with "--all". Drop this and instead clear the flag yourself as you visit commits.

See revision 3. I now re-walk the tree as needed. Performance under --all is now extremely good (but does not stream).

Quoted 11 lines

revision.c static void simplify_merges(struct rev_info *revs) · line 3125

Quoted 9 lines
revision.c +9 -0
+		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) {

You have some whitespace issues. Put a space between "while" and "(". Same with "if"s below.

(See revision 3). I think I got them all.

Quoted 9 lines

revision.c static void simplify_merges(struct rev_info *revs) · line 3131

Quoted 6 lines
revision.c +6 -0
+				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);

I don't think you want pop_commit() here. You want to have "parents = parents->next" at the end.

Quoted 6 lines

Now, if this is how you are "simplifying" the edges in the final output, then I think this is destructive and unsafe! You are literally modifying "commit->parents" so if another operation in Git tries to read those parents it will see the wrong data.

Think about a different way to achieve your goal here, perhaps in the rendering portion of graph.c instead of here.

I would really like to be blissfully ignorant of branches' merge bases.

I understand that this feature interacts nontrivially with things like --boundary (and in fact does retain significant information in the ordering---see the last test case in t6016). That said, it's not clear to me the use case for this when combined with other sophisticated graph manipulations.

At the end of the day, I'm trying to make a feature that aids in visualizing the repository. Do you had an example case where someone would like to use this feature, but removing these parents makes these other options less useful?

Quoted 17 lines

revision.c static void simplify_merges(struct rev_info *revs) · line 3143

Quoted 12 lines
revision.c +12 -0
+				} 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);
+				}

It is very unclear that your loop terminates. Instead, use "parents = parents->next" at the end of the loop block to make is extremely clear that the loop behaves as expected.

Quoted 2 lines

Of course, this assumes that you are not being destructive to the commit parents as you explore.

(*parents) is a commit_list. If, at the start of an iteration of the loop, it has n items in it, by the end of that iteration, we will have either removed the head commit (via pop_commit) or advanced one item down the list. In either case, there are n-1 items in the list at the end of the iteration. Therefore, the loop must terminate.

I've slightly adjusted the layout to make this more clear.

Quoted 10 lines

revision.c static void simplify_merges(struct rev_info *revs) · line 3148

Quoted 5 lines
revision.c +5 -0
+			}
+
+			/* feed the parents, right to left (reversed) onto the
+			 * stack to do a depth-first traversal of the commit graph
+			 */

nit: multi-line comment style [1]

[1] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L285-L291

Quoted 7 lines

revision.c static void simplify_merges(struct rev_info *revs) · line 3151

Quoted 3 lines
revision.c +3 -0
+			while(list_lr) {
+				commit_list_insert(pop_commit(&list_lr), &stack);
+			}

nit: No curly braces around single-line blocks. [2]

[2] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L239-L243

Thank you (and see revision 3).

Quoted 26 lines
Quoted 26 lines
revision.c +8 -0
+		}
+	}
+
+	clear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING);
+}
+
 static void set_children(struct rev_info *revs)
 {
 	struct commit_list *l;
@@ -3392,6 +3452,8 @@ 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)
revision.h +0 -0
index c1af164b30..f1abdb26b0 100644
@@ -51,6 +51,11 @@
 #define TOPO_WALK_EXPLORED	(1u<<27)
 #define TOPO_WALK_INDEGREE	(1u<<28)
 
Quoted 9 lines

revision.h line 57

Quoted 4 lines
revision.h +4 -0
+/* Re-use the TOPO_WALK flagspace for simplify_forks
+ */
+#define SIMP_FORK_VISITED	(1u<<27)
+#define SIMP_FORK_VISITING	(1u<<28)

I don't like that you are re-using these, as it is dangerous for later collisions. At the moment, these flags are not used in the same code paths because you specify "limited = 1" and that code path does not use TOPO_WALK_* macros.

I'm happy to use a different bit, and it would make me sleep easier knowing that this code is portable without worrying about this flag. I'm now using bits 23 and 24.

Quoted 81 lines
Quoted 27 lines
revision.h +1 -0
 #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,
t/t6016-rev-list-graph-simplify-history.sh +8 -0
index f5e6e92f5b..d99214b6df 100755
@@ -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 &&

t/t6016-rev-list-graph-simplify-history.sh test_expect_success '--graph --all' ' · line 105

Quoted 10 lines
t/t6016-rev-list-graph-simplify-history.sh +10 -0
+	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 &&

Do not use too many echos like this. Instead use t4215-log-skewed-merges.sh as an example [3].

[3] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/t/t4215-log-skewed-merges.sh#L24-L37

I also hope that you can find more complicated cases to test, including:

1. A merge that brings in a merge (think a feature branch)
2. A merge that brings in a twisted merge (think a user using "git pull").

Here are some example --graph and --simplify-forks outputs to try. I have not tested these myself, but I believe they are interesting test cases that can trip up other algorithms.

Merge bringing a merge (non-twisted):

--graph --simplify-forks
* *

 |\		|\
 | *		| *
 | |\		| |\
 | | *		| | *
 | * |		| *
 * | |		*
 |/ /		*

* / *
|/
*

Twisted merge:

--graph --simplify-forks
* *

 |\		|\
 | *		| *
 | |\		| *
 | * |		*
 | | |		*
 * |/		*
 |/|
 * |
 |/
Quoted 1 line

*

That is much nicer. I've cleaned up t6106 in a similar way, and test --ignore-merge-bases there, t4215, and in the new t4216.

Thanks,
Antonio

#10 lore raw

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

In reply to Antonio Russo

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

---
 t/t6016-rev-list-graph-simplify-history.sh | 349 ++++++++++-----------
 1 file changed, 166 insertions(+), 183 deletions(-)
t/t6016-rev-list-graph-simplify-history.sh +166 -183
index f5e6e92f5b..eac271a4fa 100755
@@ -9,6 +9,12 @@ test_description='--graph and simplified history'
 
 . ./test-lib.sh
 
+check_graph () {
+	cat >expected &&
+	git rev-list --graph "$@" | sed "$(cat sedscript)" > actual &&
+	test_cmp expected actual
+}
+
 test_expect_success 'set up rev-list --graph test' '
 	# 3 commits on branch A
 	test_commit A1 foo.txt &&
@@ -43,76 +49,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)
-	'
+	echo "s/ *$//;" > sedscript &&
+	( for tag in $(git tag -l) ; do echo "s/$(git rev-parse --verify $tag)/$tag/;" >> sedscript ; done )
+'
 
 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 +114,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
Signature · 1 line
2.26.2
#13 lore raw

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

In reply to Antonio Russo

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.

---
 Documentation/rev-list-options.txt |  9 ++++
 object.h                           |  2 +-
 revision.c                         | 85 ++++++++++++++++++++++++++++++
 revision.h                         |  5 ++
 4 files changed, 100 insertions(+), 1 deletion(-)
Documentation/rev-list-options.txt +9 -0
index 04ad7dd36e..3f5d196985 100644
@@ -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
object.h +1 -1
index b22328b838..0bf6fb0d55 100644
@@ -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
revision.c +85 -0

103 lines not on this page · raw message

revision.h +5 -0
index c1af164b30..93b318b304 100644
@@ -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,
Signature · 1 line
2.26.2
#16 lore raw

PATCH v3 3/3 Add new tests of ignore-merge-bases

In reply to Antonio Russo

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

Add the new test case t4216-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.

---
 t/t4215-log-skewed-merges.sh               | 165 +++++++++++++
 t/t4216-log-merges.sh                      | 273 +++++++++++++++++++++
 t/t6016-rev-list-graph-simplify-history.sh |  69 ++++++
 3 files changed, 507 insertions(+)
 create mode 100755 t/t4216-log-merges.sh
t/t4215-log-skewed-merges.sh +165 -0
index 28d0779a8c..fb5df1a323 100755
@@ -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,27 @@ 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 +502,37 @@ 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_A
+	| | | |  /
+	| | | | | *   7_M4
+	| |_|_|_|/|\
+	|/| | | |/ /
+	| | |_|/| /
+	| |/| | |/
+	| | | |/|
+	| | |/| |
+	| | * | | 7_G
+	| | | |/
+	| | |/|
+	| | * | 7_F
+	| |  /
+	| * / 7_E
+	| |/
+	| * 7_D
+	* 7_C
+	* 7_B
+	EOF
+'
+
 test_done
t/t4216-log-merges.sh new file +273 -0

273 lines not on this page · raw message

t/t6016-rev-list-graph-simplify-history.sh +69 -0

91 lines not on this page · raw message

Signature · 1 line
2.26.2
#9 lore raw
In reply to Antonio Russo
Quoted 95 lines · Antonio Russo
Quoted 10 lines · Derrick Stolee
Quoted 8 lines · Antonio Russo

When used with --graph, instead of displaying the full graph, display a spanning subgraph produced by a depth-first search of the graph visiting parents from left to right. Edges to already visited commits are discarded. This process is repeated for every commit to be displayed.

This is valuable to reduce visual clutter when there are many merges that were not rebased onto each other and the user is primarily interested in the state of the branch being merged into.

Quoted 8 lines

My earlier comment to recommend how to fix the test failures intended to demonstrate that this area of code requires a bit of precision. I took some time to review this patch, but I find it needs some significant updates.

tl;dr: The way you manipulate the commit parents seems incorrect to me, but perhaps there is enough prior art in the way we simplify parents to make that acceptable. Someone else will need to chime in on that part.

First, thank you for taking the time look at this. I understand your hesitation about the "amputation" of the history, but in some sense that's the point of this option. I really want to be ignorant of the details of when the fork branched off. I would like the reported history to be appear nearly equivalent to a rebase-and-fastforward only merge style, which results in a much simpler git log --graph.

Quoted 3 lines

It may be possible to do this "drop edges" entirely inside of graph.c (the graph rendering code) instead of revision.c, which would automatically work with the performance gains from the newer topo-walk algorithm.

Non-local information about the commit graph needs to be used to do this amputation of the history. We cannot know how many parents we want to display until we've completely explored all the parents of that node. Unfortunately, that means that the whole graph needs to be loaded, and I cannot really see how there would be any gain by doing this in graph.c.

Caveat: there are semi-streaming DFS implementations (i.e., O(n log n) space) that we might be able to use to get the first line out the door quicker. I would, however, like to leave that to another patch.

I will also add that, for the tests I've done, all performance penalties have been insignificant (less than ~5% for showing the first commit), while there are significant performance _improvements_, e.g., ~40% for displaying the full tree.

A notable exception is --all, which can be ~50x faster for the full output, but is often dramatically slower to show anything (i.e., the first line).

Quoted 2 lines

There are enough deviations from code and test style that this will need a significant revision regardless.

(Please see forthcoming revision 3).

Quoted 6 lines
Quoted 3 lines

This second revision of the patch sets revs->limited. This forces the graph of commits to be loaded, and simplfiy_forks() therefore reliably traverses it. This addresses the test failures mentioned before (see [1]).

This will have a significant performance impact on the option, as you will not see even the first result until the DFS has completed.

First of all, short of using some other, more sophisticated streaming version of this algorithm, the full DFS must finish before the first commit having two (or more) parents can be shown.

That said, the performance is not significantly affected:

I ran the following test (2.26.2, with my patch on top of it):
(git lg = git log --graph --pretty=oneline)

% time git lg -n1 --ignore-merge-bases e896a286df > /dev/null 0.73s user 0.02s system 99% cpu 0.746 total

% time git lg -n1 e896a286df > /dev/null
0.72s user 0.01s system 99% cpu 0.731 total

For the linux git repo:

% time git lg -n1 --ignore-merge-bases v5.7-rc3 >/dev/null 9.25s user 0.39s system 99% cpu 9.646 total

% time git lg -n1 v5.7-rc3 >/dev/null
9.02s user 0.35s system 99% cpu 9.378 total

So the performance seems basically unaffected for very limited graphs. It's also about 40% faster for complicated ones (as mentioned in my first email):

% time git lg --ignore-merge-bases e870325ee8 > /dev/null 0.83s user 0.06s system 99% cpu 0.886 total

% time git lg e870325ee8 > /dev/null
1.41s user 0.03s system 99% cpu 1.443 total

Quoted 7 lines

For the linux git repo:

% time git lg --ignore-merge-bases v5.7-rc3 >/dev/null 11.86s user 0.62s system 99% cpu 12.489 total

% time git lg v5.7-rc3 >/dev/null
21.56s user 0.55s system 99% cpu 22.108 total

First, run git commit-graph write --reachable to create a commit-graph file which has generation numbers. In this case, I get the following:

$ time git log --oneline --graph v5.7-rc3 >/dev/null
real    0m13.548s
user    0m13.348s
sys     0m0.200s
$ time git log --oneline --graph -n 1 v5.7-rc3 >/dev/null
real    0m0.007s
user    0m0.004s
sys     0m0.004s

Notice exactly how much better this gets for the first result with that file.

Quoted 13 lines

This is because the amputated graph is much simpler, and the rest of the code needs to do much less work.

Passing --all is another beast, and does indeed suffer:

% time git lg --ignore-merge-bases --all >/dev/null 4.06s user 0.04s system 99% cpu 4.105 total

% time git lg --all >/dev/null
189.59s user 0.04s system 99% cpu 3:09.65 total

(and for the first line)

Quoted 8 lines

% time git lg -n1 --ignore-merge-bases --all >/dev/null 3.86s user 0.02s system 99% cpu 3.874 total

% time git lg -n1 --all >/dev/null
0.83s user 0.02s system 99% cpu 0.848 total

(If you need to use --all for the Linux git repo, you should not use --ignore-merge-bases).

I think this is a deficiency in your implementation, not a hard rule about how these options would need to interact.

Thanks,
-Stolee

#11 lore raw

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

In reply to Antonio Russo

t/t6016-rev-list-graph-simplify-history.sh test_description='--graph and simplified history' · line 13

Quoted 2 lines · Antonio Russo
t/t6016-rev-list-graph-simplify-history.sh +2 -0
+check_graph () {
+	cat >expected &&

Not a new issue, but we may want to fix this to align to majority of tests by calling it "expect".

t/t6016-rev-list-graph-simplify-history.sh test_description='--graph and simplified history' · line 14

Quoted 1 line
t/t6016-rev-list-graph-simplify-history.sh +1 -0
+	git rev-list --graph "$@" | sed "$(cat sedscript)" > actual &&

Style. No SP between > (or < for that matter) and the filename.

The "sed" utility can be told to read its script from a file with its "-f" option.

Correctness. Never run "git" command that is the target being tested on the left side of a pipe. It will hide the exit status.

Quoted 17 lines
t/t6016-rev-list-graph-simplify-history.sh +2 -7
+	test_cmp expected actual
+}
 
 test_expect_success 'set up rev-list --graph test' '
 	# 3 commits on branch A
 	test_commit A1 foo.txt &&
@@ -43,76 +49,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) &&

t/t6016-rev-list-graph-simplify-history.sh test_expect_success 'set up rev-list --graph test' ' · line 53

Quoted 10 lines
t/t6016-rev-list-graph-simplify-history.sh +2 -8
-	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)
-	'
+	echo "s/ *$//;" > sedscript &&
+	( for tag in $(git tag -l) ; do echo "s/$(git rev-parse --verify $tag)/$tag/;" >> sedscript ; done )

Avoid unreadable one-liner with needless subshell.

I suspect that this is a task for-each-ref was designed for, something along the lines of...

	git for-each-ref --format='s|%(objectname)|%(refname:short)|' \
		refs/tags/ >>sedScript
Quoted 39 lines
t/t6016-rev-list-graph-simplify-history.sh +13 -24
+'
 
 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

t/t6016-rev-list-graph-simplify-history.sh test_expect_success 'set up rev-list --graph test' ' · line 78

Quoted 10 lines
t/t6016-rev-list-graph-simplify-history.sh +10 -0
+	| | * C1
+	| * | B2
+	| * | B1
+	* | | A3
+	| |/
+	|/|
+	* | A2
+	|/
+	* A1
+	EOF

Much nicer to see.

Having said all that, I am not sure if this change of design is sound.

The original approach would have worked even if two or more of these tags pointed at the same object. Your version will pick one of them. If two tags, say A5 and C8, pointed at the same commit, and the illustration given to check_graph helper from its standard output labeled a commit as C8, wouldn't the actual output converted to show A5 with your sedScript approach?

I think it is salvageable by changing the direction you munge. Instead of munging the rev-list output, you can store it as-is in "actual", and instead pass the illustration that comes from the standard input of the check_graph helper through sed to expand the symbolic names to actual object names before comparing. i.e.

	check_graph () {
		sed -f expand_tag_to_objects.sed >expect &&
		git rev-list --graph "$@" >actual &&
		test_cmp expect actual
	}

Note that I renamed the overly generic "sedscript" to a name that reflects the purpose of the file (and the contents being of a certain type is conveyed by .sed suffix, just like you'd use suffixes like .c, .txt). A good discipline to learn, I would say.

Thanks.

#14 lore raw

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

In reply to Antonio Russo

Am 01.05.20 um 16:22 schrieb Antonio Russo:

Documentation/rev-list-options.txt Default mode:: · line 373

Quoted 8 lines

+--ignore-merge-bases::

Documentation/rev-list-options.txt +7 -0
+	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`.

I wonder whether there is some potential to prettify another aspect of --graph once this feature is in place: In particular, when I *am* interested in merge-bases, I use --boundary, and I get this chart:

$ git log --graph --boundary --oneline --no-decorate 7d28d69174~4..7d28d69174

* 7d28d69174 Merge branch 'jc/allow-strlen-substitution-in-shell-scripts'
|\
| * 78725ebda9 CodingGuidelines: allow ${#posix} == strlen($posix)
* | dfdce31ce6 Merge branch 'en/pull-do-not-rebase-after-fast-forwarding'

|\ \  
| * | fbae70ddc6 pull: avoid running both merge and rebase
| |/  
* |   b660a76d0f Merge branch 'dl/wrapper-fix-indentation'
|\ \  
| * | 7cd54d37dc wrapper: indent with tabs
* | |   3d6c56dd66 Merge branch 'ag/sequencer-i18n-messages'
|\ \ \  
| * | | 4d55d63bde sequencer: mark messages for translation
| o | | 3bab5d5625 The second batch post 2.26 cycle
|  / /  

o / / 9f471e4b95 Merge branch 'rs/pull-options-sync-code-and-doc' / /
o / 0b6806b9e4 xread, xwrite: limit size of IO to 8MB
/
o b6d4d82bd5 msvc: accommodate for vcpkg's upgrade to OpenSSL v1.1.x

but I would prefer to see something like this:

* 7d28d69174 Merge branch 'jc/allow-strlen-substitution-in-shell-scripts'
|\
| * 78725ebda9 CodingGuidelines: allow ${#posix} == strlen($posix)
* | dfdce31ce6 Merge branch 'en/pull-do-not-rebase-after-fast-forwarding'

|\ \  
| * | fbae70ddc6 pull: avoid running both merge and rebase
| |/
| o b6d4d82bd5 msvc: accommodate for vcpkg's upgrade to OpenSSL v1.1.x  
*   b660a76d0f Merge branch 'dl/wrapper-fix-indentation'
|\  
| * 7cd54d37dc wrapper: indent with tabs
| o 0b6806b9e4 xread, xwrite: limit size of IO to 8MB
*   3d6c56dd66 Merge branch 'ag/sequencer-i18n-messages'
|\  
| * 4d55d63bde sequencer: mark messages for translation
| o 3bab5d5625 The second batch post 2.26 cycle

o 9f471e4b95 Merge branch 'rs/pull-options-sync-code-and-doc'

Maybe that is just an easy fall-out?

object.h struct object_array { · line 62

Quoted 10 lines
object.h +1 -1
index b22328b838..0bf6fb0d55 100644
@@ -59,7 +59,7 @@ struct object_array {
 
 /*
  * object flag allocation:
- * revision.h:               0---------10         15                   25----28
+ * revision.h:               0---------10         15                   23----28

I think the intent is that the line is like a ruler with marks: you should move "23" sufficiently far to the left, because the "23" mark cannot be at the same spot where the "25" mark was.

(I'm not reviewing this patch as I am illiterate when it comes to the revision walker, I just happened to notice this when I skimmed the patch.)

object.h struct object_array { · line 65

Quoted 3 lines
object.h +0 -0
  * fetch-pack.c:             01
  * negotiator/default.c:       2--5
  * walker.c:                 0-2

-- Hannes

#15 lore raw

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

Quoted 55 lines · Johannes Sixt

Am 01.05.20 um 16:22 schrieb Antonio Russo:

Documentation/rev-list-options.txt Default mode:: · line 373

Quoted 8 lines

+--ignore-merge-bases::

Documentation/rev-list-options.txt +7 -0
+	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`.

I wonder whether there is some potential to prettify another aspect of --graph once this feature is in place: In particular, when I *am* interested in merge-bases, I use --boundary, and I get this chart:

$ git log --graph --boundary --oneline --no-decorate 7d28d69174~4..7d28d69174

* 7d28d69174 Merge branch 'jc/allow-strlen-substitution-in-shell-scripts'
|\
| * 78725ebda9 CodingGuidelines: allow ${#posix} == strlen($posix)
* | dfdce31ce6 Merge branch 'en/pull-do-not-rebase-after-fast-forwarding'

|\ \  
| * | fbae70ddc6 pull: avoid running both merge and rebase
| |/  
* |   b660a76d0f Merge branch 'dl/wrapper-fix-indentation'
|\ \  
| * | 7cd54d37dc wrapper: indent with tabs
* | |   3d6c56dd66 Merge branch 'ag/sequencer-i18n-messages'
|\ \ \  
| * | | 4d55d63bde sequencer: mark messages for translation
| o | | 3bab5d5625 The second batch post 2.26 cycle
|  / /  

o / / 9f471e4b95 Merge branch 'rs/pull-options-sync-code-and-doc' / /
o / 0b6806b9e4 xread, xwrite: limit size of IO to 8MB
/
o b6d4d82bd5 msvc: accommodate for vcpkg's upgrade to OpenSSL v1.1.x

but I would prefer to see something like this:

* 7d28d69174 Merge branch 'jc/allow-strlen-substitution-in-shell-scripts'
|\
| * 78725ebda9 CodingGuidelines: allow ${#posix} == strlen($posix)
* | dfdce31ce6 Merge branch 'en/pull-do-not-rebase-after-fast-forwarding'

|\ \  
| * | fbae70ddc6 pull: avoid running both merge and rebase
| |/
| o b6d4d82bd5 msvc: accommodate for vcpkg's upgrade to OpenSSL v1.1.x  
*   b660a76d0f Merge branch 'dl/wrapper-fix-indentation'
|\  
| * 7cd54d37dc wrapper: indent with tabs
| o 0b6806b9e4 xread, xwrite: limit size of IO to 8MB
*   3d6c56dd66 Merge branch 'ag/sequencer-i18n-messages'
|\  
| * 4d55d63bde sequencer: mark messages for translation
| o 3bab5d5625 The second batch post 2.26 cycle
Quoted 3 lines

o 9f471e4b95 Merge branch 'rs/pull-options-sync-code-and-doc'

Maybe that is just an easy fall-out?

Yeah, I noticed this too. What we want is to create a spanning tree by left-first DFS (amputating edges connecting to already visited vertices), and then walk the amputated tree in a right-first DFS (and then not sort the commits any further).

The tricky part is getting the results of the right-first DFS before the left-first (amputation) DFS finishes. I'm working on it.

Quoted 6 lines
Quoted 6 lines
object.h +0 -0
index b22328b838..0bf6fb0d55 100644
@@ -59,7 +59,7 @@ struct object_array {
 
Quoted 8 lines

object.h struct object_array { · line 62

Quoted 4 lines
object.h +1 -1
 /*
  * object flag allocation:
- * revision.h:               0---------10         15                   25----28
+ * revision.h:               0---------10         15                   23----28

I think the intent is that the line is like a ruler with marks: you should move "23" sufficiently far to the left, because the "23" mark cannot be at the same spot where the "25" mark was.

I though this was only a schematic ruler, but, counting it now, it is exact. I'll fix it.

Quoted 3 lines

(I'm not reviewing this patch as I am illiterate when it comes to the revision walker, I just happened to notice this when I skimmed the patch.)

Thank you,
Antonio

#12 lore raw

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

In reply to Junio C Hamano
Quoted 24 lines · Junio C Hamano

t/t6016-rev-list-graph-simplify-history.sh test_description='--graph and simplified history' · line 13

Quoted 2 lines · Antonio Russo
t/t6016-rev-list-graph-simplify-history.sh +2 -0
+check_graph () {
+	cat >expected &&

Not a new issue, but we may want to fix this to align to majority of tests by calling it "expect".

t/t6016-rev-list-graph-simplify-history.sh test_description='--graph and simplified history' · line 14

Quoted 1 line
t/t6016-rev-list-graph-simplify-history.sh +1 -0
+	git rev-list --graph "$@" | sed "$(cat sedscript)" > actual &&

Style. No SP between > (or < for that matter) and the filename.

The "sed" utility can be told to read its script from a file with its "-f" option.

Correctness. Never run "git" command that is the target being tested on the left side of a pipe. It will hide the exit status.

t/t6016-rev-list-graph-simplify-history.sh test_expect_success 'set up rev-list --graph test' ' · line 53

Quoted 3 lines
t/t6016-rev-list-graph-simplify-history.sh +2 -1
-	'
+	echo "s/ *$//;" > sedscript &&
+	( for tag in $(git tag -l) ; do echo "s/$(git rev-parse --verify $tag)/$tag/;" >> sedscript ; done )

Avoid unreadable one-liner with needless subshell.

Quoted 6 lines

I suspect that this is a task for-each-ref was designed for, something along the lines of...

	git for-each-ref --format='s|%(objectname)|%(refname:short)|' \
		refs/tags/ >>sedScript

Thanks, I've fixed these.

Quoted 25 lines

Much nicer to see.

Having said all that, I am not sure if this change of design is sound.

The original approach would have worked even if two or more of these tags pointed at the same object. Your version will pick one of them. If two tags, say A5 and C8, pointed at the same commit, and the illustration given to check_graph helper from its standard output labeled a commit as C8, wouldn't the actual output converted to show A5 with your sedScript approach?

I think it is salvageable by changing the direction you munge. Instead of munging the rev-list output, you can store it as-is in "actual", and instead pass the illustration that comes from the standard input of the check_graph helper through sed to expand the symbolic names to actual object names before comparing. i.e.

	check_graph () {
		sed -f expand_tag_to_objects.sed >expect &&
		git rev-list --graph "$@" >actual &&
		test_cmp expect actual
	}
Quoted 4 lines

Note that I renamed the overly generic "sedscript" to a name that reflects the purpose of the file (and the contents being of a certain type is conveyed by .sed suffix, just like you'd use suffixes like .c, .txt). A good discipline to learn, I would say.

I also fixed these. I originally chose the other direction (oid->refname) to make the output more human readable.

If you think that's a worthwhile goal, I can figure something out.

That said, the patchset as it stands scratches my immediate need, and addressing D. Stolee's comments (in particular, making it work with revs->limited==0) unfortunately has to be a lower priority for me.

I am not abandoning the patchset, but may be more delayed responding to review.

Thanks,
Antonio