patchTeach git-rev-list --simplify-forks

> * 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'
> |\
> | * 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'

> * 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'
> |\ \ \ \
> | * | | | 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'
> |\ \ \ \

> === 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.

> On 4/27/20 4:55 AM, Derrick Stolee wrote:
>>
>> 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)?

> 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.
>
> Signed-off-by: Antonio Russo <antonio.e.russo@gmail.com>
> ---
>  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
>
> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
> index 04ad7dd36e..cbac09028c 100644
> --- a/Documentation/rev-list-options.txt
> +++ b/Documentation/rev-list-options.txt
> @@ -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
> diff --git a/revision.c b/revision.c
> index 5bc96444b6..51dbe21847 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
>  		revs->simplify_by_decoration = 1;
>  		revs->limited = 1;
>  		revs->prune = 1;
> +	} else if (!strcmp(arg, "--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)
> diff --git a/revision.h b/revision.h
> index c1af164b30..f1abdb26b0 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -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,
> diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh
> index f5e6e92f5b..d99214b6df 100755
> --- a/t/t6016-rev-list-graph-simplify-history.sh
> +++ b/t/t6016-rev-list-graph-simplify-history.sh
> @@ -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 &&

>> +--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

> --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.

> 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.

> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
> index 04ad7dd36e..cbac09028c 100644
> --- a/Documentation/rev-list-options.txt
> +++ b/Documentation/rev-list-options.txt
> @@ -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
> diff --git a/revision.c b/revision.c
> index 5bc96444b6..51dbe21847 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
>  		revs->simplify_by_decoration = 1;
>  		revs->limited = 1;
>  		revs->prune = 1;
> +	} else if (!strcmp(arg, "--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) {

> +		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
> +			 */

> +		}
> +	}
> +
> +	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)
> diff --git a/revision.h b/revision.h
> index c1af164b30..f1abdb26b0 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -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,
> diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh
> index f5e6e92f5b..d99214b6df 100755
> --- a/t/t6016-rev-list-graph-simplify-history.sh
> +++ b/t/t6016-rev-list-graph-simplify-history.sh
> @@ -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 &&

> On 4/29/2020 4:01 AM, Antonio Russo wrote:
>> 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.

>> 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.

>> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
>> index 04ad7dd36e..cbac09028c 100644
>> --- a/Documentation/rev-list-options.txt
>> +++ b/Documentation/rev-list-options.txt
>> @@ -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.

>>  --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/revision.c b/revision.c
>> index 5bc96444b6..51dbe21847 100644
>> --- a/revision.c
>> +++ b/revision.c
>> @@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
>>  		revs->simplify_by_decoration = 1;
>>  		revs->limited = 1;
>>  		revs->prune = 1;
>> +	} else if (!strcmp(arg, "--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.

>>  	} 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.

>> +	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.

>> +		/* 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.

>> +		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.

>> +				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.

>> +				} 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.

>> +			}
>> +
>> +			/* 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
>
>> +			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

>> +		}
>> +	}
>> +
>> +	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)
>> diff --git a/revision.h b/revision.h
>> index c1af164b30..f1abdb26b0 100644
>> --- a/revision.h
>> +++ b/revision.h
>> @@ -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.

>>  #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,
>> diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh
>> index f5e6e92f5b..d99214b6df 100755
>> --- a/t/t6016-rev-list-graph-simplify-history.sh
>> +++ b/t/t6016-rev-list-graph-simplify-history.sh
>> @@ -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 &&
>
> 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
>  *		*
>  |\		|\
>  | *		| *
>  | |\		| *
>  | * |		*
>  | | |		*
>  * |/		*
>  |/|
>  * |
>  |/
>  *

> On 4/29/20 7:12 AM, Derrick Stolee wrote:
>> On 4/29/2020 4:01 AM, Antonio Russo wrote:
>>> 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.
> 
> 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.
> 
>> 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).
> 
>> There are enough deviations from code and test style that this will
>> need a significant revision regardless.
> 
> (Please see forthcoming revision 3).
> 
>>> 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).

>  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

> Antonio Russo <antonio.e.russo@gmail.com> writes:
> 
>> +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".
> 
>> +	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.

>> -	'
>> +	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
> 

> 
> 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.

> +--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`.

> diff --git a/object.h b/object.h
> index b22328b838..0bf6fb0d55 100644
> --- a/object.h
> +++ b/object.h
> @@ -59,7 +59,7 @@ struct object_array {
> 
>  /*
>   * object flag allocation:
> - * revision.h:               0---------10         15                   25----28
> + * revision.h:               0---------10         15                   23----28

> Am 01.05.20 um 16:22 schrieb Antonio Russo:
>> +--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`.
> 
> 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?

>> diff --git a/object.h b/object.h
>> index b22328b838..0bf6fb0d55 100644
>> --- a/object.h
>> +++ b/object.h
>> @@ -59,7 +59,7 @@ struct object_array {
>>
>>  /*
>>   * object flag allocation:
>> - * revision.h:               0---------10         15                   25----28
>> + * revision.h:               0---------10         15                   23----28
> 
> 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.