{"thread":{"id":"53330","subject":"[PATCH] Teach git-rev-list --simplify-forks","startedAt":"2020-04-27T05:07:12Z","lastAt":"2020-05-02T15:27:50Z","messageCount":17,"participants":["Antonio Russo","Derrick Stolee","Philip Oakley","Junio C Hamano","Johannes Sixt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"396316","messageId":"df0b9e59-e6d7-8839-ca3b-86145dc3bdf3@gmail.com","threadId":"53330","inReplyTo":null,"subject":"[PATCH] Teach git-rev-list --simplify-forks","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-04-27T05:07:08Z","receivedAt":"2020-04-27T05:07:12Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"When used with --graph, instead of displaying the full graph, display a\nspanning subgraph produced by a depth-first search of the graph visiting\nparents from left to right.  Edges to already visited commits are\ndiscarded.  This process is repeated for every commit to be displayed.\n\nThis is valuable to reduce visual clutter when there are many merges\nthat were not rebased onto each other and the user is primarily\ninterested in the state of the branch being merged into.\n\nAlso adds documentation and tests of the above.\n\nSigned-off-by: Antonio Russo <antonio.e.russo@gmail.com>\n---\n Documentation/rev-list-options.txt         |  8 +++\n revision.c                                 | 67 +++++++++++++++++++++-\n revision.h                                 |  6 ++\n t/t6016-rev-list-graph-simplify-history.sh | 50 ++++++++++++++++\n 4 files changed, 130 insertions(+), 1 deletion(-)\n\nHello,\n\nI'm trying to address a long-standing problem I've had visualizing complex\ngit repositories with git log --graph.  I think that a picture is worth a\nthousand words, so I'll just show what the patch does for git master:\n\n% git log --graph --abbrev-commit --pretty=oneline --simplify-forks e870325ee8\n\n> * e870325ee8 (HEAD -> master, origin/master, origin/HEAD) The third batch\n> *   a397e9c236 Merge branch 'jk/credential-parsing-end-of-host-in-URL'\n> |\\\n> | * 4c5971e18a credential: treat \"?\" and \"#\" in URLs as end of host\n> *   d6d561db1c Merge branch 'jt/rebase-allow-duplicate'\n> |\\\n> | * 0fcb4f6b62 rebase --merge: optionally skip upstreamed commits\n> *   c7d8f69da5 Merge branch 'en/rebase-no-keep-empty'\n> |\\\n> | * 50ed76148a rebase: fix an incompatible-options error message\n> | * b9cbd2958f rebase: reinstate --no-keep-empty\n> | * 1b5735f75c rebase -i: mark commits that begin empty in todo editor\n> *   8b39dfdf47 Merge branch 'js/mingw-is-hidden-test-fix'\n> |\\\n> | * 176a66a748 t: restrict `is_hidden` to be called only on Windows\n> | * 9814d0a4ad mingw: make test_path_is_hidden more robust\n> | * 7c2dfca7e8 t: consolidate the `is_hidden` functions\n> *   a41b41ca74 Merge branch 'js/mingw-isilon-nfs'\n> |\\\n> | * 23eafd924a mingw: cope with the Isilon network file system\n> *   33feaca6bf Merge branch 'js/flush-prompt-before-interative-input'\n> |\\\n> | * 1f09aed834 interactive: explicitly `fflush` stdout before expecting input\n> | * 08d383f23e interactive: refactor code asking the user for interactive input\n> *   9af3a7cb4d Merge branch 'ds/revision-show-pulls'\n> |\\\n> | * 8d049e182e revision: --show-pulls adds helpful merges\n> *   82fa169d55 Merge branch 'ma/simplify-merge-config-parsing'\n> |\\\n> | * 9881b451f3 merge: use skip_prefix to parse config key\n> *   b3eb70e0f8 Merge branch 'js/mingw-fixes'\n\nCompare this to before:\n\n% git log --graph --abbrev-commit --pretty=oneline e870325ee8\n\n> * e870325ee8 (HEAD -> master, origin/master, origin/HEAD) The third batch\n> *   a397e9c236 Merge branch 'jk/credential-parsing-end-of-host-in-URL'\n> |\\\n> | * 4c5971e18a credential: treat \"?\" and \"#\" in URLs as end of host\n> * |   d6d561db1c Merge branch 'jt/rebase-allow-duplicate'\n> |\\ \\\n> | * | 0fcb4f6b62 rebase --merge: optionally skip upstreamed commits\n> * | | c7d8f69da5 Merge branch 'en/rebase-no-keep-empty'\n> |\\| |\n> | * | 50ed76148a rebase: fix an incompatible-options error message\n> | * | b9cbd2958f rebase: reinstate --no-keep-empty\n> | * | 1b5735f75c rebase -i: mark commits that begin empty in todo editor\n> * | |   8b39dfdf47 Merge branch 'js/mingw-is-hidden-test-fix'\n> |\\ \\ \\\n> | * | | 176a66a748 t: restrict `is_hidden` to be called only on Windows\n> | * | | 9814d0a4ad mingw: make test_path_is_hidden more robust\n> | * | | 7c2dfca7e8 t: consolidate the `is_hidden` functions\n> * | | |   a41b41ca74 Merge branch 'js/mingw-isilon-nfs'\n> |\\ \\ \\ \\\n> | * | | | 23eafd924a mingw: cope with the Isilon network file system\n> | |/ / /\n> * | | |   33feaca6bf Merge branch 'js/flush-prompt-before-interative-input'\n> |\\ \\ \\ \\\n> | * | | | 1f09aed834 interactive: explicitly `fflush` stdout before expecting input\n> | * | | | 08d383f23e interactive: refactor code asking the user for interactive input\n> | |/ / /\n> * | | |   9af3a7cb4d Merge branch 'ds/revision-show-pulls'\n> |\\ \\ \\ \\\n> | * | | | 8d049e182e revision: --show-pulls adds helpful merges\n> | |/ / /\n> * | | |   82fa169d55 Merge branch 'ma/simplify-merge-config-parsing'\n> |\\ \\ \\ \\\n> | * | | | 9881b451f3 merge: use skip_prefix to parse config key\n> | |/ / /\n> * | | |   b3eb70e0f8 Merge branch 'js/mingw-fixes'\n> |\\ \\ \\ \\\n\nRoughly, the tool produces a spanning tree by traversing the commit graph,\nleftmost parents first. It forgets information about where forks occurred,\nremoving the \"tails\" that connect branches back to their original fork\npoint.  These \"tails\" can be very long and often do not contain information\nthat is very important for someone glancing through commits.\n\n=== Details\n\nIt's about 40% faster.  Tested this on current master (of git):\n\ngit log --graph --pretty=oneline --simplify-forks e870325ee8 > /dev/null  0.83s user 0.06s system 99% cpu 0.886 total\n\ngit log --graph --pretty=oneline e870325ee8 > /dev/null  1.41s user 0.03s system 99% cpu 1.443 total\n\nThis is because the produced graph is much simpler---it is a tree in the\nabove case (though not in general).\n\nThe exact approach uses two flags (reusing bits 27 and 28 that are used\nby the topological sort walk).  One says whether the commit has been ever\nvisited, and the other says whether the commit was visited from the current\nroot.  The walk does not continue down any commit that was visited, and\nleaves the connection to the parent only if has not been visited from the\ncurrent root.  Each commit that is to be shown is treated as its own root\n(most of these root commits are immediately skipped, because they are\nlikely visited in an earlier traversal).\n\n=== Problems\n\nTravis CI is showing issues with the tests I've added [1].  I cannot\nreproduce them locally, neither with gcc 4.8.5 (RHEL) nor 9.3.0 (Debian).\nThey're also only failing on one of the runners.\n\n\nThank you for taking the time to look at this,\nAntonio Russo\n\n\n[1] https://travis-ci.org/github/aerusso/git\n[2] https://github.com/aerusso/git/tree/mrs/simplify-history-forks\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 04ad7dd36e..cbac09028c 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -363,6 +363,14 @@ Default mode::\n \tmerges from the resulting history, as there are no selected\n \tcommits contributing to this merge.\n\n+--simplify-forks::\n+\tConvert the commit graph into a spanning subgraph produced by a\n+\tdepth-first-search of the history graph, searching the leftmost\n+\tparent first, and discarding edges to commits already visited.\n+\tUseful with `--graph` to visualize repositories with many merges\n+\twhen you are interested in was added to master, and not when the\n+\tbranch was last rebased.\n+\n --ancestry-path::\n \tWhen given a range of commits to display (e.g. 'commit1..commit2'\n \tor 'commit2 {caret}commit1'), only display commits that exist\ndiff --git a/revision.c b/revision.c\nindex 5bc96444b6..06d9697306 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2082,6 +2082,8 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->simplify_by_decoration = 1;\n \t\trevs->limited = 1;\n \t\trevs->prune = 1;\n+\t} else if (!strcmp(arg, \"--simplify-forks\")) {\n+\t\trevs->simplify_forks = 1;\n \t} else if (!strcmp(arg, \"--date-order\")) {\n \t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n \t\trevs->topo_order = 1;\n@@ -3095,6 +3097,63 @@ static void simplify_merges(struct rev_info *revs)\n \t}\n }\n\n+static void simplify_forks(struct rev_info *revs)\n+{\n+\tstruct commit_list *stack, *list_lr, *iter_list;\n+\tstruct commit_list **parents;\n+\tstruct commit *commit, *parent;\n+\n+\tstack = NULL;\n+\tlist_lr = NULL;\n+\n+\tclear_object_flags(SIMP_FORK_VISITED);\n+\n+\tfor(iter_list = revs->commits; iter_list; iter_list = iter_list->next) {\n+\t\t/* process every commit to be displayed exactly once */\n+\t\tif(iter_list->item->object.flags & SIMP_FORK_VISITED)\n+\t\t\tcontinue;\n+\t\tclear_object_flags(SIMP_FORK_VISITING);\n+\t\tcommit_list_insert(iter_list->item, &stack);\n+\t\titer_list->item->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING;\n+\t\twhile(stack) {\n+\t\t\tcommit = pop_commit(&stack);\n+\t\t\t/* process the parent nodes: removing links to\n+\t\t\t * commits already visited (creating a spanning tree)\n+\t\t\t */\n+\t\t\tparents = &(commit->parents);\n+\t\t\twhile(*parents) {\n+\t\t\t\tparent = (*parents)->item;\n+\t\t\t\tif(parent->object.flags & SIMP_FORK_VISITING) {\n+\t\t\t\t\t/* We have already visited this commit, from the same root.\n+\t\t\t\t\t * We do not explore it at all.\n+\t\t\t\t\t */\n+\t\t\t\t\tpop_commit(parents);\n+\t\t\t\t} else if(parent->object.flags & SIMP_FORK_VISITED) {\n+\t\t\t\t\t/* We visited this commit before, but from a different root.\n+\t\t\t\t\t * Leave it attached, but do not explore it further.\n+\t\t\t\t\t */\n+\t\t\t\t\tparents = &((*parents)->next);\n+\t\t\t\t} else {\n+\t\t\t\t\t/* We have not visited this commit yet. Explore it, as usual.\n+\t\t\t\t\t */\n+\t\t\t\t\tparent->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING;\n+\t\t\t\t\tcommit_list_insert(parent, &list_lr);\n+\t\t\t\t\tparents = &((*parents)->next);\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\t/* feed the parents, right to left (reversed) onto the\n+\t\t\t * stack to do a depth-first traversal of the commit graph\n+\t\t\t */\n+\t\t\twhile(list_lr) {\n+\t\t\t\tcommit_list_insert(pop_commit(&list_lr), &stack);\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tclear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING);\n+}\n+\n static void set_children(struct rev_info *revs)\n {\n \tstruct commit_list *l;\n@@ -3392,10 +3451,16 @@ int prepare_revision_walk(struct rev_info *revs)\n \tif (revs->limited) {\n \t\tif (limit_list(revs) < 0)\n \t\t\treturn -1;\n+\t\tif (revs->simplify_forks)\n+\t\t\tsimplify_forks(revs);\n \t\tif (revs->topo_order)\n \t\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n-\t} else if (revs->topo_order)\n+\t} else if (revs->topo_order) {\n+\t\tif (revs->simplify_forks)\n+\t\t\tsimplify_forks(revs);\n \t\tinit_topo_walk(revs);\n+\t} else if (revs->simplify_forks)\n+\t\tsimplify_forks(revs);\n \tif (revs->line_level_traverse)\n \t\tline_log_filter(revs);\n \tif (revs->simplify_merges)\ndiff --git a/revision.h b/revision.h\nindex c1af164b30..f1abdb26b0 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -51,6 +51,11 @@\n #define TOPO_WALK_EXPLORED\t(1u<<27)\n #define TOPO_WALK_INDEGREE\t(1u<<28)\n\n+/* Re-use the TOPO_WALK flagspace for simplify_forks\n+ */\n+#define SIMP_FORK_VISITED\t(1u<<27)\n+#define SIMP_FORK_VISITING\t(1u<<28)\n+\n #define DECORATE_SHORT_REFS\t1\n #define DECORATE_FULL_REFS\t2\n\n@@ -132,6 +137,7 @@ struct rev_info {\n \t\t\tno_walk:2,\n \t\t\tremove_empty_trees:1,\n \t\t\tsimplify_history:1,\n+\t\t\tsimplify_forks:1,\n \t\t\tshow_pulls:1,\n \t\t\ttopo_order:1,\n \t\t\tsimplify_merges:1,\ndiff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh\nindex f5e6e92f5b..d99214b6df 100755\n--- a/t/t6016-rev-list-graph-simplify-history.sh\n+++ b/t/t6016-rev-list-graph-simplify-history.sh\n@@ -85,6 +85,28 @@ test_expect_success '--graph --all' '\n \ttest_cmp expected actual\n \t'\n\n+# Make sure that simplify_histpry_forks produces a spanning tree\n+test_expect_success '--graph --simplify-forks --all' '\n+\trm -f expected &&\n+\techo \"* $A7\" >> expected &&\n+\techo \"*   $A6\" >> expected &&\n+\techo \"|\\  \" >> expected &&\n+\techo \"| * $C4\" >> expected &&\n+\techo \"| * $C3\" >> expected &&\n+\techo \"* $A5\" >> expected &&\n+\techo \"*-.   $A4\" >> expected &&\n+\techo \"|\\ \\  \" >> expected &&\n+\techo \"| | * $C2\" >> expected &&\n+\techo \"| | * $C1\" >> expected &&\n+\techo \"| * $B2\" >> expected &&\n+\techo \"| * $B1\" >> expected &&\n+\techo \"* $A3\" >> expected &&\n+\techo \"* $A2\" >> expected &&\n+\techo \"* $A1\" >> expected &&\n+\tgit rev-list --graph --simplify-forks --all > actual &&\n+\ttest_cmp expected actual\n+\t'\n+\n # Make sure the graph_is_interesting() code still realizes\n # that undecorated merges are interesting, even with --simplify-by-decoration\n test_expect_success '--graph --simplify-by-decoration' '\n@@ -157,6 +179,20 @@ test_expect_success '--graph --full-history -- bar.txt' '\n \ttest_cmp expected actual\n \t'\n\n+test_expect_success '--graph --simplify-forks --full-history -- bar.txt' '\n+\trm -f expected &&\n+\techo \"* $A7\" >> expected &&\n+\techo \"*   $A6\" >> expected &&\n+\techo \"|\\\\  \" >> expected &&\n+\techo \"| * $C4\" >> expected &&\n+\techo \"* $A5\" >> expected &&\n+\techo \"* $A4\" >> expected &&\n+\techo \"* $A3\" >> expected &&\n+\techo \"* $A2\" >> expected &&\n+\tgit rev-list --graph --simplify-forks --full-history --all -- bar.txt > actual &&\n+\ttest_cmp expected actual\n+\t'\n+\n test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '\n \trm -f expected &&\n \techo \"* $A7\" >> expected &&\n@@ -172,6 +208,20 @@ test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '\n \ttest_cmp expected actual\n \t'\n\n+test_expect_success '--graph --simplify-forks --full-history --simplify-merges -- bar.txt' '\n+\trm -f expected &&\n+\techo \"* $A7\" >> expected &&\n+\techo \"*   $A6\" >> expected &&\n+\techo \"|\\\\  \" >> expected &&\n+\techo \"| * $C4\" >> expected &&\n+\techo \"* $A5\" >> expected &&\n+\techo \"* $A3\" >> expected &&\n+\techo \"* $A2\" >> expected &&\n+\tgit rev-list --graph --simplify-forks --full-history --simplify-merges --all \\\n+\t\t-- bar.txt > actual &&\n+\ttest_cmp expected actual\n+\t'\n+\n test_expect_success '--graph -- bar.txt' '\n \trm -f expected &&\n \techo \"* $A7\" >> expected &&\n-- \n2.26.2\n\n"},{"id":"396321","messageId":"4ee983f6-402f-85bb-25a8-75b39f07cabb@gmail.com","threadId":"53330","inReplyTo":"df0b9e59-e6d7-8839-ca3b-86145dc3bdf3@gmail.com","subject":"Re: [PATCH] Teach git-rev-list --simplify-forks","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-27T10:55:03Z","receivedAt":"2020-04-27T10:55:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/27/2020 1:07 AM, Antonio Russo wrote:\n> === Problems\n> \n> Travis CI is showing issues with the tests I've added [1].  I cannot\n> reproduce them locally, neither with gcc 4.8.5 (RHEL) nor 9.3.0 (Debian).\n> They're also only failing on one of the runners.\n\nThis 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.\n\nThanks,\n-Stolee\n\n\n"},{"id":"396457","messageId":"070c07f6-5b36-89e7-a9fe-9bd321fcb97e@gmail.com","threadId":"53330","inReplyTo":"4ee983f6-402f-85bb-25a8-75b39f07cabb@gmail.com","subject":"Re: [PATCH] Teach git-rev-list --simplify-forks","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-04-28T12:49:00Z","receivedAt":"2020-04-28T12:49:04Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"On 4/27/20 4:55 AM, Derrick Stolee wrote:\n> \n> 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.\n> \n\nThank you for pointing me at this.  If I now understand correctly, the commit information\nis not yet necessarily loaded for all commits at this point, and therefore the logic here\nwill need to be called later on (and makes it more complicated).\n\nAm I correct that this loading of parents happens during traverse_commit_list_filtered\n(for the case of rev-list)?  Also, am I correct that there are not yet any hooks to\nfilter out edges (of the graph of commits)?\n\nThank you,\nAntonio\n"},{"id":"396462","messageId":"155e3be2-1852-3590-2cd9-c868fa5a696a@gmail.com","threadId":"53330","inReplyTo":"070c07f6-5b36-89e7-a9fe-9bd321fcb97e@gmail.com","subject":"Re: [PATCH] Teach git-rev-list --simplify-forks","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-28T14:11:22Z","receivedAt":"2020-04-28T14:11:28Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/28/2020 8:49 AM, Antonio Russo wrote:\n> On 4/27/20 4:55 AM, Derrick Stolee wrote:\n>>\n>> 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.\n>>\n> \n> Thank you for pointing me at this.  If I now understand correctly, the commit information\n> is not yet necessarily loaded for all commits at this point, and therefore the logic here\n> will need to be called later on (and makes it more complicated).\n> \n> Am I correct that this loading of parents happens during traverse_commit_list_filtered\n> (for the case of rev-list)?  Also, am I correct that there are not yet any hooks to\n> filter out edges (of the graph of commits)?\n\nI mean that if you have a commit-graph, then a completely disjoint set of code\nis run instead of the code you modified. See [1] for the blocks of code that\nare run instead.\n\n[1] https://github.com/git/git/commit/b45424181e9e8b2284a48c6db7b8db635bbfccc8\n\nThanks,\n-Stolee\n"},{"id":"396528","messageId":"d3079ba8-33e1-3b68-23d2-ea97b9ca1e97@gmail.com","threadId":"53330","inReplyTo":"df0b9e59-e6d7-8839-ca3b-86145dc3bdf3@gmail.com","subject":"[PATCH v2] Teach git-rev-list --simplify-forks","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-04-29T08:01:25Z","receivedAt":"2020-04-29T08:01:34Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"When used with --graph, instead of displaying the full graph, display a\nspanning subgraph produced by a depth-first search of the graph visiting\nparents from left to right.  Edges to already visited commits are\ndiscarded.  This process is repeated for every commit to be displayed.\n\nThis is valuable to reduce visual clutter when there are many merges\nthat were not rebased onto each other and the user is primarily\ninterested in the state of the branch being merged into.\n\nAlso adds documentation and tests of the above.\n\nSigned-off-by: Antonio Russo <antonio.e.russo@gmail.com>\n---\n Documentation/rev-list-options.txt         |  8 +++\n revision.c                                 | 62 ++++++++++++++++++++++\n revision.h                                 |  6 +++\n t/t6016-rev-list-graph-simplify-history.sh | 50 +++++++++++++++++\n 4 files changed, 126 insertions(+)\n\nHello,\n\nThis second revision of the patch sets revs->limited.  This forces the\ngraph of commits to be loaded, and simplfiy_forks() therefore reliably\ntraverses it.  This addresses the test failures mentioned before (see [1]).\n\nAntonio\n\n[1] https://travis-ci.org/github/aerusso/git/builds/680894920\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 04ad7dd36e..cbac09028c 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -363,6 +363,14 @@ Default mode::\n \tmerges from the resulting history, as there are no selected\n \tcommits contributing to this merge.\n\n+--simplify-forks::\n+\tConvert the commit graph into a spanning subgraph produced by a\n+\tdepth-first-search of the history graph, searching the leftmost\n+\tparent first, and discarding edges to commits already visited.\n+\tUseful with `--graph` to visualize repositories with many merges\n+\twhen you are interested in was added to master, and not when the\n+\tbranch was last rebased.\n+\n --ancestry-path::\n \tWhen given a range of commits to display (e.g. 'commit1..commit2'\n \tor 'commit2 {caret}commit1'), only display commits that exist\ndiff --git a/revision.c b/revision.c\nindex 5bc96444b6..51dbe21847 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->simplify_by_decoration = 1;\n \t\trevs->limited = 1;\n \t\trevs->prune = 1;\n+\t} else if (!strcmp(arg, \"--simplify-forks\")) {\n+\t\trevs->limited = 1;\n+\t\trevs->simplify_forks = 1;\n \t} else if (!strcmp(arg, \"--date-order\")) {\n \t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n \t\trevs->topo_order = 1;\n@@ -3095,6 +3098,63 @@ static void simplify_merges(struct rev_info *revs)\n \t}\n }\n\n+static void simplify_forks(struct rev_info *revs)\n+{\n+\tstruct commit_list *stack, *list_lr, *iter_list;\n+\tstruct commit_list **parents;\n+\tstruct commit *commit, *parent;\n+\n+\tstack = NULL;\n+\tlist_lr = NULL;\n+\n+\tclear_object_flags(SIMP_FORK_VISITED);\n+\n+\tfor(iter_list = revs->commits; iter_list; iter_list = iter_list->next) {\n+\t\t/* process every commit to be displayed exactly once */\n+\t\tif(iter_list->item->object.flags & SIMP_FORK_VISITED)\n+\t\t\tcontinue;\n+\t\tclear_object_flags(SIMP_FORK_VISITING);\n+\t\tcommit_list_insert(iter_list->item, &stack);\n+\t\titer_list->item->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING;\n+\t\twhile(stack) {\n+\t\t\tcommit = pop_commit(&stack);\n+\t\t\t/* process the parent nodes: removing links to\n+\t\t\t * commits already visited (creating a spanning tree)\n+\t\t\t */\n+\t\t\tparents = &(commit->parents);\n+\t\t\twhile(*parents) {\n+\t\t\t\tparent = (*parents)->item;\n+\t\t\t\tif(parent->object.flags & SIMP_FORK_VISITING) {\n+\t\t\t\t\t/* We have already visited this commit, from the same root.\n+\t\t\t\t\t * We do not explore it at all.\n+\t\t\t\t\t */\n+\t\t\t\t\tpop_commit(parents);\n+\t\t\t\t} else if(parent->object.flags & SIMP_FORK_VISITED) {\n+\t\t\t\t\t/* We visited this commit before, but from a different root.\n+\t\t\t\t\t * Leave it attached, but do not explore it further.\n+\t\t\t\t\t */\n+\t\t\t\t\tparents = &((*parents)->next);\n+\t\t\t\t} else {\n+\t\t\t\t\t/* We have not visited this commit yet. Explore it, as usual.\n+\t\t\t\t\t */\n+\t\t\t\t\tparent->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING;\n+\t\t\t\t\tcommit_list_insert(parent, &list_lr);\n+\t\t\t\t\tparents = &((*parents)->next);\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\t/* feed the parents, right to left (reversed) onto the\n+\t\t\t * stack to do a depth-first traversal of the commit graph\n+\t\t\t */\n+\t\t\twhile(list_lr) {\n+\t\t\t\tcommit_list_insert(pop_commit(&list_lr), &stack);\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tclear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING);\n+}\n+\n static void set_children(struct rev_info *revs)\n {\n \tstruct commit_list *l;\n@@ -3392,6 +3452,8 @@ int prepare_revision_walk(struct rev_info *revs)\n \tif (revs->limited) {\n \t\tif (limit_list(revs) < 0)\n \t\t\treturn -1;\n+\t\tif (revs->simplify_forks)\n+\t\t\tsimplify_forks(revs);\n \t\tif (revs->topo_order)\n \t\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n \t} else if (revs->topo_order)\ndiff --git a/revision.h b/revision.h\nindex c1af164b30..f1abdb26b0 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -51,6 +51,11 @@\n #define TOPO_WALK_EXPLORED\t(1u<<27)\n #define TOPO_WALK_INDEGREE\t(1u<<28)\n\n+/* Re-use the TOPO_WALK flagspace for simplify_forks\n+ */\n+#define SIMP_FORK_VISITED\t(1u<<27)\n+#define SIMP_FORK_VISITING\t(1u<<28)\n+\n #define DECORATE_SHORT_REFS\t1\n #define DECORATE_FULL_REFS\t2\n\n@@ -132,6 +137,7 @@ struct rev_info {\n \t\t\tno_walk:2,\n \t\t\tremove_empty_trees:1,\n \t\t\tsimplify_history:1,\n+\t\t\tsimplify_forks:1,\n \t\t\tshow_pulls:1,\n \t\t\ttopo_order:1,\n \t\t\tsimplify_merges:1,\ndiff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh\nindex f5e6e92f5b..d99214b6df 100755\n--- a/t/t6016-rev-list-graph-simplify-history.sh\n+++ b/t/t6016-rev-list-graph-simplify-history.sh\n@@ -85,6 +85,28 @@ test_expect_success '--graph --all' '\n \ttest_cmp expected actual\n \t'\n\n+# Make sure that simplify_histpry_forks produces a spanning tree\n+test_expect_success '--graph --simplify-forks --all' '\n+\trm -f expected &&\n+\techo \"* $A7\" >> expected &&\n+\techo \"*   $A6\" >> expected &&\n+\techo \"|\\  \" >> expected &&\n+\techo \"| * $C4\" >> expected &&\n+\techo \"| * $C3\" >> expected &&\n+\techo \"* $A5\" >> expected &&\n+\techo \"*-.   $A4\" >> expected &&\n+\techo \"|\\ \\  \" >> expected &&\n+\techo \"| | * $C2\" >> expected &&\n+\techo \"| | * $C1\" >> expected &&\n+\techo \"| * $B2\" >> expected &&\n+\techo \"| * $B1\" >> expected &&\n+\techo \"* $A3\" >> expected &&\n+\techo \"* $A2\" >> expected &&\n+\techo \"* $A1\" >> expected &&\n+\tgit rev-list --graph --simplify-forks --all > actual &&\n+\ttest_cmp expected actual\n+\t'\n+\n # Make sure the graph_is_interesting() code still realizes\n # that undecorated merges are interesting, even with --simplify-by-decoration\n test_expect_success '--graph --simplify-by-decoration' '\n@@ -157,6 +179,20 @@ test_expect_success '--graph --full-history -- bar.txt' '\n \ttest_cmp expected actual\n \t'\n\n+test_expect_success '--graph --simplify-forks --full-history -- bar.txt' '\n+\trm -f expected &&\n+\techo \"* $A7\" >> expected &&\n+\techo \"*   $A6\" >> expected &&\n+\techo \"|\\\\  \" >> expected &&\n+\techo \"| * $C4\" >> expected &&\n+\techo \"* $A5\" >> expected &&\n+\techo \"* $A4\" >> expected &&\n+\techo \"* $A3\" >> expected &&\n+\techo \"* $A2\" >> expected &&\n+\tgit rev-list --graph --simplify-forks --full-history --all -- bar.txt > actual &&\n+\ttest_cmp expected actual\n+\t'\n+\n test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '\n \trm -f expected &&\n \techo \"* $A7\" >> expected &&\n@@ -172,6 +208,20 @@ test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '\n \ttest_cmp expected actual\n \t'\n\n+test_expect_success '--graph --simplify-forks --full-history --simplify-merges -- bar.txt' '\n+\trm -f expected &&\n+\techo \"* $A7\" >> expected &&\n+\techo \"*   $A6\" >> expected &&\n+\techo \"|\\\\  \" >> expected &&\n+\techo \"| * $C4\" >> expected &&\n+\techo \"* $A5\" >> expected &&\n+\techo \"* $A3\" >> expected &&\n+\techo \"* $A2\" >> expected &&\n+\tgit rev-list --graph --simplify-forks --full-history --simplify-merges --all \\\n+\t\t-- bar.txt > actual &&\n+\ttest_cmp expected actual\n+\t'\n+\n test_expect_success '--graph -- bar.txt' '\n \trm -f expected &&\n \techo \"* $A7\" >> expected &&\n-- \n2.26.2\n\n"},{"id":"396535","messageId":"eda71f1e-b883-82c3-72f2-dc5221804c4b@iee.email","threadId":"53330","inReplyTo":"d3079ba8-33e1-3b68-23d2-ea97b9ca1e97@gmail.com","subject":"Re: [PATCH v2] Teach git-rev-list --simplify-forks","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2020-04-29T10:08:12Z","receivedAt":"2020-04-29T10:08:20Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Hi Antonio,\n\nOn 29/04/2020 09:01, Antonio Russo wrote:\n> When used with --graph, instead of displaying the full graph, display a\n> spanning subgraph produced by a depth-first search of the graph visiting\n> parents from left to right.  Edges to already visited commits are\n> discarded.  This process is repeated for every commit to be displayed.\n>\n> This is valuable to reduce visual clutter when there are many merges\n> that were not rebased onto each other and the user is primarily\n> interested in the state of the branch being merged into.\n>\n> Also adds documentation and tests of the above.\n>\n> Signed-off-by: Antonio Russo <antonio.e.russo@gmail.com>\n> ---\n>  Documentation/rev-list-options.txt         |  8 +++\n>  revision.c                                 | 62 ++++++++++++++++++++++\n>  revision.h                                 |  6 +++\n>  t/t6016-rev-list-graph-simplify-history.sh | 50 +++++++++++++++++\n>  4 files changed, 126 insertions(+)\n>\n> Hello,\n>\n> This second revision of the patch sets revs->limited.  This forces the\n> graph of commits to be loaded, and simplfiy_forks() therefore reliably\n> traverses it.  This addresses the test failures mentioned before (see [1]).\n>\n> Antonio\n>\n> [1] https://travis-ci.org/github/aerusso/git/builds/680894920\n>\n> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> index 04ad7dd36e..cbac09028c 100644\n> --- a/Documentation/rev-list-options.txt\n> +++ b/Documentation/rev-list-options.txt\n> @@ -363,6 +363,14 @@ Default mode::\n>  \tmerges from the resulting history, as there are no selected\n>  \tcommits contributing to this merge.\n>\n> +--simplify-forks::\n> +\tConvert the commit graph into a spanning subgraph produced by a\n> +\tdepth-first-search of the history graph, searching the leftmost\n> +\tparent first, and discarding edges to commits already visited.\n> +\tUseful with `--graph` to visualize repositories with many merges\n> +\twhen you are interested in was added to master, and not when the\n> +\tbranch was last rebased.\n\nDoes this also need to actually mention that it effectively discard\nedges to fork points, as per the option name?. No rebasing required for\nit to be useful.\n     s/when/where/\n    \"...and not where the branch was last rebased or forked from.\" - not\ngreat but actually mentions the option.\n\n--\nPhilip\n> +\n>  --ancestry-path::\n>  \tWhen given a range of commits to display (e.g. 'commit1..commit2'\n>  \tor 'commit2 {caret}commit1'), only display commits that exist\n> diff --git a/revision.c b/revision.c\n> index 5bc96444b6..51dbe21847 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n>  \t\trevs->simplify_by_decoration = 1;\n>  \t\trevs->limited = 1;\n>  \t\trevs->prune = 1;\n> +\t} else if (!strcmp(arg, \"--simplify-forks\")) {\n> +\t\trevs->limited = 1;\n> +\t\trevs->simplify_forks = 1;\n>  \t} else if (!strcmp(arg, \"--date-order\")) {\n>  \t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n>  \t\trevs->topo_order = 1;\n> @@ -3095,6 +3098,63 @@ static void simplify_merges(struct rev_info *revs)\n>  \t}\n>  }\n>\n> +static void simplify_forks(struct rev_info *revs)\n> +{\n> +\tstruct commit_list *stack, *list_lr, *iter_list;\n> +\tstruct commit_list **parents;\n> +\tstruct commit *commit, *parent;\n> +\n> +\tstack = NULL;\n> +\tlist_lr = NULL;\n> +\n> +\tclear_object_flags(SIMP_FORK_VISITED);\n> +\n> +\tfor(iter_list = revs->commits; iter_list; iter_list = iter_list->next) {\n> +\t\t/* process every commit to be displayed exactly once */\n> +\t\tif(iter_list->item->object.flags & SIMP_FORK_VISITED)\n> +\t\t\tcontinue;\n> +\t\tclear_object_flags(SIMP_FORK_VISITING);\n> +\t\tcommit_list_insert(iter_list->item, &stack);\n> +\t\titer_list->item->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING;\n> +\t\twhile(stack) {\n> +\t\t\tcommit = pop_commit(&stack);\n> +\t\t\t/* process the parent nodes: removing links to\n> +\t\t\t * commits already visited (creating a spanning tree)\n> +\t\t\t */\n> +\t\t\tparents = &(commit->parents);\n> +\t\t\twhile(*parents) {\n> +\t\t\t\tparent = (*parents)->item;\n> +\t\t\t\tif(parent->object.flags & SIMP_FORK_VISITING) {\n> +\t\t\t\t\t/* We have already visited this commit, from the same root.\n> +\t\t\t\t\t * We do not explore it at all.\n> +\t\t\t\t\t */\n> +\t\t\t\t\tpop_commit(parents);\n> +\t\t\t\t} else if(parent->object.flags & SIMP_FORK_VISITED) {\n> +\t\t\t\t\t/* We visited this commit before, but from a different root.\n> +\t\t\t\t\t * Leave it attached, but do not explore it further.\n> +\t\t\t\t\t */\n> +\t\t\t\t\tparents = &((*parents)->next);\n> +\t\t\t\t} else {\n> +\t\t\t\t\t/* We have not visited this commit yet. Explore it, as usual.\n> +\t\t\t\t\t */\n> +\t\t\t\t\tparent->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING;\n> +\t\t\t\t\tcommit_list_insert(parent, &list_lr);\n> +\t\t\t\t\tparents = &((*parents)->next);\n> +\t\t\t\t}\n> +\t\t\t}\n> +\n> +\t\t\t/* feed the parents, right to left (reversed) onto the\n> +\t\t\t * stack to do a depth-first traversal of the commit graph\n> +\t\t\t */\n> +\t\t\twhile(list_lr) {\n> +\t\t\t\tcommit_list_insert(pop_commit(&list_lr), &stack);\n> +\t\t\t}\n> +\t\t}\n> +\t}\n> +\n> +\tclear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING);\n> +}\n> +\n>  static void set_children(struct rev_info *revs)\n>  {\n>  \tstruct commit_list *l;\n> @@ -3392,6 +3452,8 @@ int prepare_revision_walk(struct rev_info *revs)\n>  \tif (revs->limited) {\n>  \t\tif (limit_list(revs) < 0)\n>  \t\t\treturn -1;\n> +\t\tif (revs->simplify_forks)\n> +\t\t\tsimplify_forks(revs);\n>  \t\tif (revs->topo_order)\n>  \t\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n>  \t} else if (revs->topo_order)\n> diff --git a/revision.h b/revision.h\n> index c1af164b30..f1abdb26b0 100644\n> --- a/revision.h\n> +++ b/revision.h\n> @@ -51,6 +51,11 @@\n>  #define TOPO_WALK_EXPLORED\t(1u<<27)\n>  #define TOPO_WALK_INDEGREE\t(1u<<28)\n>\n> +/* Re-use the TOPO_WALK flagspace for simplify_forks\n> + */\n> +#define SIMP_FORK_VISITED\t(1u<<27)\n> +#define SIMP_FORK_VISITING\t(1u<<28)\n> +\n>  #define DECORATE_SHORT_REFS\t1\n>  #define DECORATE_FULL_REFS\t2\n>\n> @@ -132,6 +137,7 @@ struct rev_info {\n>  \t\t\tno_walk:2,\n>  \t\t\tremove_empty_trees:1,\n>  \t\t\tsimplify_history:1,\n> +\t\t\tsimplify_forks:1,\n>  \t\t\tshow_pulls:1,\n>  \t\t\ttopo_order:1,\n>  \t\t\tsimplify_merges:1,\n> diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh\n> index f5e6e92f5b..d99214b6df 100755\n> --- a/t/t6016-rev-list-graph-simplify-history.sh\n> +++ b/t/t6016-rev-list-graph-simplify-history.sh\n> @@ -85,6 +85,28 @@ test_expect_success '--graph --all' '\n>  \ttest_cmp expected actual\n>  \t'\n>\n> +# Make sure that simplify_histpry_forks produces a spanning tree\n> +test_expect_success '--graph --simplify-forks --all' '\n> +\trm -f expected &&\n> +\techo \"* $A7\" >> expected &&\n> +\techo \"*   $A6\" >> expected &&\n> +\techo \"|\\  \" >> expected &&\n> +\techo \"| * $C4\" >> expected &&\n> +\techo \"| * $C3\" >> expected &&\n> +\techo \"* $A5\" >> expected &&\n> +\techo \"*-.   $A4\" >> expected &&\n> +\techo \"|\\ \\  \" >> expected &&\n> +\techo \"| | * $C2\" >> expected &&\n> +\techo \"| | * $C1\" >> expected &&\n> +\techo \"| * $B2\" >> expected &&\n> +\techo \"| * $B1\" >> expected &&\n> +\techo \"* $A3\" >> expected &&\n> +\techo \"* $A2\" >> expected &&\n> +\techo \"* $A1\" >> expected &&\n> +\tgit rev-list --graph --simplify-forks --all > actual &&\n> +\ttest_cmp expected actual\n> +\t'\n> +\n>  # Make sure the graph_is_interesting() code still realizes\n>  # that undecorated merges are interesting, even with --simplify-by-decoration\n>  test_expect_success '--graph --simplify-by-decoration' '\n> @@ -157,6 +179,20 @@ test_expect_success '--graph --full-history -- bar.txt' '\n>  \ttest_cmp expected actual\n>  \t'\n>\n> +test_expect_success '--graph --simplify-forks --full-history -- bar.txt' '\n> +\trm -f expected &&\n> +\techo \"* $A7\" >> expected &&\n> +\techo \"*   $A6\" >> expected &&\n> +\techo \"|\\\\  \" >> expected &&\n> +\techo \"| * $C4\" >> expected &&\n> +\techo \"* $A5\" >> expected &&\n> +\techo \"* $A4\" >> expected &&\n> +\techo \"* $A3\" >> expected &&\n> +\techo \"* $A2\" >> expected &&\n> +\tgit rev-list --graph --simplify-forks --full-history --all -- bar.txt > actual &&\n> +\ttest_cmp expected actual\n> +\t'\n> +\n>  test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '\n>  \trm -f expected &&\n>  \techo \"* $A7\" >> expected &&\n> @@ -172,6 +208,20 @@ test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '\n>  \ttest_cmp expected actual\n>  \t'\n>\n> +test_expect_success '--graph --simplify-forks --full-history --simplify-merges -- bar.txt' '\n> +\trm -f expected &&\n> +\techo \"* $A7\" >> expected &&\n> +\techo \"*   $A6\" >> expected &&\n> +\techo \"|\\\\  \" >> expected &&\n> +\techo \"| * $C4\" >> expected &&\n> +\techo \"* $A5\" >> expected &&\n> +\techo \"* $A3\" >> expected &&\n> +\techo \"* $A2\" >> expected &&\n> +\tgit rev-list --graph --simplify-forks --full-history --simplify-merges --all \\\n> +\t\t-- bar.txt > actual &&\n> +\ttest_cmp expected actual\n> +\t'\n> +\n>  test_expect_success '--graph -- bar.txt' '\n>  \trm -f expected &&\n>  \techo \"* $A7\" >> expected &&\n\n"},{"id":"396553","messageId":"ceeb706d-83ad-c994-121d-d66724d82a49@gmail.com","threadId":"53330","inReplyTo":"eda71f1e-b883-82c3-72f2-dc5221804c4b@iee.email","subject":"Re: [PATCH v2] Teach git-rev-list --simplify-forks","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-04-29T13:04:41Z","receivedAt":"2020-04-29T13:04:45Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"On 4/29/20 4:08 AM, Philip Oakley wrote:\n>> +--simplify-forks::\n>> +\tConvert the commit graph into a spanning subgraph produced by a\n>> +\tdepth-first-search of the history graph, searching the leftmost\n>> +\tparent first, and discarding edges to commits already visited.\n>> +\tUseful with `--graph` to visualize repositories with many merges\n>> +\twhen you are interested in was added to master, and not when the\n>> +\tbranch was last rebased.\n> \n> Does this also need to actually mention that it effectively discard\n> edges to fork points, as per the option name?. No rebasing required for\n> it to be useful.\n>      s/when/where/\n>     \"...and not where the branch was last rebased or forked from.\" - not\n> great but actually mentions the option.\n> \n> --\n> Philip\n\nGood point.  More generally, my description of the option is not very\nuseful unless you already basically understand what it's doing.\n\nHow about:\n\n> --simplify-forks::\n> \tOmits the parent relationship of the first commit of merged branches.\n> \tEffectively discards all information about the fork point of merged\n> \tbranches.  It does so by converting the commit graph into a\n> \tspanning subgraph produced by a depth-first-search of the history\n> \tgraph, searching the leftmost parent first, and discarding edges\n> \tto commits already visited.  Useful with `--graph` to visualize\n> \trepositories with many merges when you are most interested in\n> \twhen branches were merged.\n\n\nAntonio\n"},{"id":"396554","messageId":"08d5460b-d80b-28a3-19dd-d438afbdfba9@gmail.com","threadId":"53330","inReplyTo":"d3079ba8-33e1-3b68-23d2-ea97b9ca1e97@gmail.com","subject":"Re: [PATCH v2] Teach git-rev-list --simplify-forks","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-29T13:12:55Z","receivedAt":"2020-04-29T13:13:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/29/2020 4:01 AM, Antonio Russo wrote:\n> When used with --graph, instead of displaying the full graph, display a\n> spanning subgraph produced by a depth-first search of the graph visiting\n> parents from left to right.  Edges to already visited commits are\n> discarded.  This process is repeated for every commit to be displayed.\n> \n> This is valuable to reduce visual clutter when there are many merges\n> that were not rebased onto each other and the user is primarily\n> interested in the state of the branch being merged into.\n\nMy earlier comment to recommend how to fix the test failures intended\nto demonstrate that this area of code requires a bit of precision. I\ntook some time to review this patch, but I find it needs some significant\nupdates.\n\ntl;dr: The way you manipulate the commit parents seems incorrect to me,\nbut perhaps there is enough prior art in the way we simplify parents to\nmake that acceptable. Someone else will need to chime in on that part.\n\nIt may be possible to do this \"drop edges\" entirely inside of graph.c\n(the graph rendering code) instead of revision.c, which would automatically\nwork with the performance gains from the newer topo-walk algorithm.\n\nThere are enough deviations from code and test style that this will\nneed a significant revision regardless.\n \n> This second revision of the patch sets revs->limited.  This forces the\n> graph of commits to be loaded, and simplfiy_forks() therefore reliably\n> traverses it.  This addresses the test failures mentioned before (see [1]).\n\nThis will have a significant performance impact on the option, as you will\nnot see even the first result until the DFS has completed.\n\n> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> index 04ad7dd36e..cbac09028c 100644\n> --- a/Documentation/rev-list-options.txt\n> +++ b/Documentation/rev-list-options.txt\n> @@ -363,6 +363,14 @@ Default mode::\n>  \tmerges from the resulting history, as there are no selected\n>  \tcommits contributing to this merge.\n> \n> +--simplify-forks::\n> +\tConvert the commit graph into a spanning subgraph produced by a\n> +\tdepth-first-search of the history graph, searching the leftmost\n> +\tparent first, and discarding edges to commits already visited.\n> +\tUseful with `--graph` to visualize repositories with many merges\n> +\twhen you are interested in was added to master, and not when the\n> +\tbranch was last rebased.\n\nDescribing the option via the algorithm may not be the best way to\ninform the user of what they will see. It also will not be informative\nif the implementation changes to not perform the algorithm described\nhere, because that algorithm is not incremental (it is O(N) where N is\nthe total number of reachable commits, not ~O(n) where n is the number\nof commits that will actually show up).\n\nAn easy test is to time your command with \"-n 1\".\n\nI'm also not crazy about \"when the branch was last rebased\". You\nprobably mean \"..when you are not interested in which merge base\nwas used for each merge.\"\n\nAlso, this does nothing without \"--graph\" right? Perhaps it should\nenable it?\n\nHere is a suggested alternative:\n\n--simplify-forks::\n\tShow commits that are introduced by each merge before showing\n\tthe first parent of the merge, as in `--graph`, but remove\n\tedges from those commits to commits reachable from the first\n\tparent. This helps to visualize repositories with many merges\n\twhen you are not interested in which merge base was used for\n\teach merge. It also reduces the width of the graph visualization\n\tcompared to `--graph`.\n\nWith this description, perhaps it is worth renaming the option? Perhaps\n\"--ignore-merge-bases\"? The word \"simplify\" implies something like\ndropping commits from history, but you are instead dropping _edges_ from\nthe graph.\n\n>  --ancestry-path::\n>  \tWhen given a range of commits to display (e.g. 'commit1..commit2'\n>  \tor 'commit2 {caret}commit1'), only display commits that exist\n> diff --git a/revision.c b/revision.c\n> index 5bc96444b6..51dbe21847 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n>  \t\trevs->simplify_by_decoration = 1;\n>  \t\trevs->limited = 1;\n>  \t\trevs->prune = 1;\n> +\t} else if (!strcmp(arg, \"--simplify-forks\")) {\n> +\t\trevs->limited = 1;\n> +\t\trevs->simplify_forks = 1;\n\nI recommend dropping the revs->limited setting here and instead fixing the\nperformance instead. But maybe that should be a second patch on top of this\none.\n\n>  \t} else if (!strcmp(arg, \"--date-order\")) {\n>  \t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n>  \t\trevs->topo_order = 1;\n> @@ -3095,6 +3098,63 @@ static void simplify_merges(struct rev_info *revs)\n>  \t}\n>  }\n> \n> +static void simplify_forks(struct rev_info *revs)\n> +{\n> +\tstruct commit_list *stack, *list_lr, *iter_list;\n> +\tstruct commit_list **parents;\n\nYou want \"struct commit_list *parents\" here for simpler use.\n\n> +\tstruct commit *commit, *parent;\n> +\n> +\tstack = NULL;\n> +\tlist_lr = NULL;\n> +\n> +\tclear_object_flags(SIMP_FORK_VISITED);\n> +\n> +\tfor(iter_list = revs->commits; iter_list; iter_list = iter_list->next) {\n\nThis method could use a split into at least two. I count three levels of nested\nloops here, so please break them up into smaller methods.\n\n> +\t\t/* process every commit to be displayed exactly once */\n> +\t\tif(iter_list->item->object.flags & SIMP_FORK_VISITED)\n> +\t\t\tcontinue;\n> +\t\tclear_object_flags(SIMP_FORK_VISITING);\n\nThis drops the flag from all commits. This will cause quadratic performance\nif combined with \"--all\". Drop this and instead clear the flag yourself as you\nvisit commits.\n\n> +\t\tcommit_list_insert(iter_list->item, &stack);\n> +\t\titer_list->item->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING;\n> +\t\twhile(stack) {\n> +\t\t\tcommit = pop_commit(&stack);\n> +\t\t\t/* process the parent nodes: removing links to\n> +\t\t\t * commits already visited (creating a spanning tree)\n> +\t\t\t */\n> +\t\t\tparents = &(commit->parents);\n> +\t\t\twhile(*parents) {\n\nYou have some whitespace issues. Put a space between \"while\" and \"(\". Same with \"if\"s below.\n\n> +\t\t\t\tparent = (*parents)->item;\n> +\t\t\t\tif(parent->object.flags & SIMP_FORK_VISITING) {\n> +\t\t\t\t\t/* We have already visited this commit, from the same root.\n> +\t\t\t\t\t * We do not explore it at all.\n> +\t\t\t\t\t */\n> +\t\t\t\t\tpop_commit(parents);\n\nI don't think you want pop_commit() here. You want to have \"parents = parents->next\" at the end.\n\nNow, if this is how you are \"simplifying\" the edges in the final output, then I think this is\ndestructive and unsafe! You are literally modifying \"commit->parents\" so if another operation in\nGit tries to read those parents it will see the wrong data.\n\nThink about a different way to achieve your goal here, perhaps in the rendering portion of\ngraph.c instead of here.\n\n> +\t\t\t\t} else if(parent->object.flags & SIMP_FORK_VISITED) {\n> +\t\t\t\t\t/* We visited this commit before, but from a different root.\n> +\t\t\t\t\t * Leave it attached, but do not explore it further.\n> +\t\t\t\t\t */\n> +\t\t\t\t\tparents = &((*parents)->next);\n> +\t\t\t\t} else {\n> +\t\t\t\t\t/* We have not visited this commit yet. Explore it, as usual.\n> +\t\t\t\t\t */\n> +\t\t\t\t\tparent->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING;\n> +\t\t\t\t\tcommit_list_insert(parent, &list_lr);\n> +\t\t\t\t\tparents = &((*parents)->next);\n> +\t\t\t\t}\n\nIt is very unclear that your loop terminates. Instead, use\n\"parents = parents->next\" at the end of the loop block to\nmake is extremely clear that the loop behaves as expected.\n\nOf course, this assumes that you are not being destructive\nto the commit parents as you explore.\n\n> +\t\t\t}\n> +\n> +\t\t\t/* feed the parents, right to left (reversed) onto the\n> +\t\t\t * stack to do a depth-first traversal of the commit graph\n> +\t\t\t */\n\nnit: multi-line comment style [1]\n\n[1] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L285-L291\n\n> +\t\t\twhile(list_lr) {\n> +\t\t\t\tcommit_list_insert(pop_commit(&list_lr), &stack);\n> +\t\t\t}\n\nnit: No curly braces around single-line blocks. [2]\n\n[2] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L239-L243\n\n> +\t\t}\n> +\t}\n> +\n> +\tclear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING);\n> +}\n> +\n>  static void set_children(struct rev_info *revs)\n>  {\n>  \tstruct commit_list *l;\n> @@ -3392,6 +3452,8 @@ int prepare_revision_walk(struct rev_info *revs)\n>  \tif (revs->limited) {\n>  \t\tif (limit_list(revs) < 0)\n>  \t\t\treturn -1;\n> +\t\tif (revs->simplify_forks)\n> +\t\t\tsimplify_forks(revs);\n>  \t\tif (revs->topo_order)\n>  \t\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n>  \t} else if (revs->topo_order)\n> diff --git a/revision.h b/revision.h\n> index c1af164b30..f1abdb26b0 100644\n> --- a/revision.h\n> +++ b/revision.h\n> @@ -51,6 +51,11 @@\n>  #define TOPO_WALK_EXPLORED\t(1u<<27)\n>  #define TOPO_WALK_INDEGREE\t(1u<<28)\n> \n> +/* Re-use the TOPO_WALK flagspace for simplify_forks\n> + */\n> +#define SIMP_FORK_VISITED\t(1u<<27)\n> +#define SIMP_FORK_VISITING\t(1u<<28)\n\nI don't like that you are re-using these, as it is dangerous for later\ncollisions. At the moment, these flags are not used in the same code paths\nbecause you specify \"limited = 1\" and that code path does not use TOPO_WALK_*\nmacros.\n\n>  #define DECORATE_SHORT_REFS\t1\n>  #define DECORATE_FULL_REFS\t2\n> \n> @@ -132,6 +137,7 @@ struct rev_info {\n>  \t\t\tno_walk:2,\n>  \t\t\tremove_empty_trees:1,\n>  \t\t\tsimplify_history:1,\n> +\t\t\tsimplify_forks:1,\n>  \t\t\tshow_pulls:1,\n>  \t\t\ttopo_order:1,\n>  \t\t\tsimplify_merges:1,\n> diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh\n> index f5e6e92f5b..d99214b6df 100755\n> --- a/t/t6016-rev-list-graph-simplify-history.sh\n> +++ b/t/t6016-rev-list-graph-simplify-history.sh\n> @@ -85,6 +85,28 @@ test_expect_success '--graph --all' '\n>  \ttest_cmp expected actual\n>  \t'\n> \n> +# Make sure that simplify_histpry_forks produces a spanning tree\n> +test_expect_success '--graph --simplify-forks --all' '\n> +\trm -f expected &&\n> +\techo \"* $A7\" >> expected &&\n> +\techo \"*   $A6\" >> expected &&\n> +\techo \"|\\  \" >> expected &&\n> +\techo \"| * $C4\" >> expected &&\n> +\techo \"| * $C3\" >> expected &&\n> +\techo \"* $A5\" >> expected &&\n> +\techo \"*-.   $A4\" >> expected &&\n> +\techo \"|\\ \\  \" >> expected &&\n> +\techo \"| | * $C2\" >> expected &&\n> +\techo \"| | * $C1\" >> expected &&\n> +\techo \"| * $B2\" >> expected &&\n> +\techo \"| * $B1\" >> expected &&\n> +\techo \"* $A3\" >> expected &&\n> +\techo \"* $A2\" >> expected &&\n> +\techo \"* $A1\" >> expected &&\n\nDo not use too many echos like this. Instead use t4215-log-skewed-merges.sh\nas an example [3].\n\n[3] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/t/t4215-log-skewed-merges.sh#L24-L37\n\nI also hope that you can find more complicated cases to\ntest, including:\n\n 1. A merge that brings in a merge (think a feature branch)\n 2. A merge that brings in a twisted merge (think a user using \"git pull\").\n\nHere are some example --graph and --simplify-forks outputs to try. I\nhave not tested these myself, but I believe they are interesting test\ncases that can trip up other algorithms.\n\nMerge bringing a merge (non-twisted):\n\n --graph\t--simplify-forks\n *\t\t*\n |\\\t\t|\\\n | *\t\t| *\n | |\\\t\t| |\\\n | | *\t\t| | *\n | * |\t\t| *\n * | |\t\t*\n |/ /\t\t*\n * /\t\t*\n |/\n *\n\nTwisted merge:\n\n --graph\t--simplify-forks\n *\t\t*\n |\\\t\t|\\\n | *\t\t| *\n | |\\\t\t| *\n | * |\t\t*\n | | |\t\t*\n * |/\t\t*\n |/|\n * |\n |/\n *\n\nThanks,\n-Stolee\n\n"},{"id":"396747","messageId":"2a668dd2-35c0-7510-fc4d-6c44e8407a07@gmail.com","threadId":"53330","inReplyTo":"08d5460b-d80b-28a3-19dd-d438afbdfba9@gmail.com","subject":"Re: [PATCH v2] Teach git-rev-list --simplify-forks","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-05-01T14:13:45Z","receivedAt":"2020-05-01T14:13:50Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"On 4/29/20 7:12 AM, Derrick Stolee wrote:\n> On 4/29/2020 4:01 AM, Antonio Russo wrote:\n>> When used with --graph, instead of displaying the full graph, display a\n>> spanning subgraph produced by a depth-first search of the graph visiting\n>> parents from left to right.  Edges to already visited commits are\n>> discarded.  This process is repeated for every commit to be displayed.\n>>\n>> This is valuable to reduce visual clutter when there are many merges\n>> that were not rebased onto each other and the user is primarily\n>> interested in the state of the branch being merged into.\n>\n> My earlier comment to recommend how to fix the test failures intended\n> to demonstrate that this area of code requires a bit of precision. I\n> took some time to review this patch, but I find it needs some significant\n> updates.\n>\n> tl;dr: The way you manipulate the commit parents seems incorrect to me,\n> but perhaps there is enough prior art in the way we simplify parents to\n> make that acceptable. Someone else will need to chime in on that part.\n\nFirst, thank you for taking the time look at this.  I understand your\nhesitation about the \"amputation\" of the history, but in some sense\nthat's the point of this option.  I really want to be ignorant of the\ndetails of when the fork branched off.  I would like the reported\nhistory to be appear nearly equivalent to a rebase-and-fastforward only\nmerge style, which results in a much simpler git log --graph.\n\n> It may be possible to do this \"drop edges\" entirely inside of graph.c\n> (the graph rendering code) instead of revision.c, which would automatically\n> work with the performance gains from the newer topo-walk algorithm.\n\nNon-local information about the commit graph needs to be used to do this\namputation of the history.  We cannot know how many parents we want to\ndisplay until we've completely explored all the parents of that node.\nUnfortunately, that means that the whole graph needs to be loaded, and I\ncannot really see how there would be any gain by doing this in graph.c.\n\nCaveat: there are semi-streaming DFS implementations (i.e., O(n log n)\nspace) that we might be able to use to get the first line out the door\nquicker. I would, however, like to leave that to another patch.\n\nI will also add that, for the tests I've done, all performance penalties\nhave been insignificant (less than ~5% for showing the first commit),\nwhile there are significant performance _improvements_, e.g., ~40% for\ndisplaying the full tree.\n\nA notable exception is --all, which can be ~50x faster for the full\noutput, but is often dramatically slower to show anything (i.e., the\nfirst line).\n\n> There are enough deviations from code and test style that this will\n> need a significant revision regardless.\n\n(Please see forthcoming revision 3).\n\n>> This second revision of the patch sets revs->limited.  This forces the\n>> graph of commits to be loaded, and simplfiy_forks() therefore reliably\n>> traverses it.  This addresses the test failures mentioned before (see [1]).\n>\n> This will have a significant performance impact on the option, as you will\n> not see even the first result until the DFS has completed.\n\nFirst of all, short of using some other, more sophisticated streaming\nversion of this algorithm, the full DFS must finish before the first\ncommit having two (or more) parents can be shown.\n\nThat said, the performance is not significantly affected:\n\nI ran the following test (2.26.2, with my patch on top of it):\n(git lg = git log --graph --pretty=oneline)\n\n % time git lg -n1 --ignore-merge-bases e896a286df > /dev/null\n 0.73s user 0.02s system 99% cpu 0.746 total\n\n % time git lg -n1 e896a286df > /dev/null\n 0.72s user 0.01s system 99% cpu 0.731 total\n\n For the linux git repo:\n\n % time git lg -n1 --ignore-merge-bases v5.7-rc3 >/dev/null\n 9.25s user 0.39s system 99% cpu 9.646 total\n\n % time git lg -n1 v5.7-rc3 >/dev/null\n 9.02s user 0.35s system 99% cpu 9.378 total\n\nSo the performance seems basically unaffected for very limited graphs.\nIt's also about 40% faster for complicated ones (as mentioned in my\nfirst email):\n\n % time git lg --ignore-merge-bases e870325ee8 > /dev/null\n 0.83s user 0.06s system 99% cpu 0.886 total\n\n % time git lg e870325ee8 > /dev/null\n 1.41s user 0.03s system 99% cpu 1.443 total\n\n For the linux git repo:\n\n % time git lg --ignore-merge-bases v5.7-rc3 >/dev/null\n 11.86s user 0.62s system 99% cpu 12.489 total\n\n % time git lg v5.7-rc3 >/dev/null\n 21.56s user 0.55s system 99% cpu 22.108 total\n\nThis is because the amputated graph is much simpler, and the rest of the\ncode needs to do much less work.\n\nPassing --all is another beast, and does indeed suffer:\n\n % time git lg --ignore-merge-bases --all >/dev/null\n 4.06s user 0.04s system 99% cpu 4.105 total\n\n % time git lg --all >/dev/null\n 189.59s user 0.04s system 99% cpu 3:09.65 total\n\n (and for the first line)\n\n % time git lg -n1 --ignore-merge-bases --all >/dev/null\n 3.86s user 0.02s system 99% cpu 3.874 total\n\n % time git lg -n1 --all >/dev/null\n 0.83s user 0.02s system 99% cpu 0.848 total\n\n(If you need to use --all for the Linux git repo, you should not use\n--ignore-merge-bases).\n\nThere's certainly performance improvements to be desired, but they do\nnot appear except for very large repositories, and only when combined\nwith --all.\n\n>> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n>> index 04ad7dd36e..cbac09028c 100644\n>> --- a/Documentation/rev-list-options.txt\n>> +++ b/Documentation/rev-list-options.txt\n>> @@ -363,6 +363,14 @@ Default mode::\n>>  \tmerges from the resulting history, as there are no selected\n>>  \tcommits contributing to this merge.\n>>\n>> +--simplify-forks::\n>> +\tConvert the commit graph into a spanning subgraph produced by a\n>> +\tdepth-first-search of the history graph, searching the leftmost\n>> +\tparent first, and discarding edges to commits already visited.\n>> +\tUseful with `--graph` to visualize repositories with many merges\n>> +\twhen you are interested in was added to master, and not when the\n>> +\tbranch was last rebased.\n>\n> Describing the option via the algorithm may not be the best way to\n> inform the user of what they will see. It also will not be informative\n> if the implementation changes to not perform the algorithm described\n> here, because that algorithm is not incremental (it is O(N) where N is\n> the total number of reachable commits, not ~O(n) where n is the number\n> of commits that will actually show up).\n>\n> An easy test is to time your command with \"-n 1\".\n\nWhile this is true, it is not the dominant effect (see above).\n\n> I'm also not crazy about \"when the branch was last rebased\". You\n> probably mean \"..when you are not interested in which merge base\n> was used for each merge.\"\n>\n> Also, this does nothing without \"--graph\" right? Perhaps it should\n> enable it?\n\nNot quite.  The patch interacts very nicely with gitk!\n\n> Here is a suggested alternative:\n>\n> --simplify-forks::\n> \tShow commits that are introduced by each merge before showing\n> \tthe first parent of the merge, as in `--graph`, but remove\n> \tedges from those commits to commits reachable from the first\n> \tparent. This helps to visualize repositories with many merges\n> \twhen you are not interested in which merge base was used for\n> \teach merge. It also reduces the width of the graph visualization\n> \tcompared to `--graph`.\n>\n> With this description, perhaps it is worth renaming the option? Perhaps\n> \"--ignore-merge-bases\"? The word \"simplify\" implies something like\n> dropping commits from history, but you are instead dropping _edges_ from\n> the graph.\n\n(see revision 3).\n\n>>  --ancestry-path::\n>>  \tWhen given a range of commits to display (e.g. 'commit1..commit2'\n>>  \tor 'commit2 {caret}commit1'), only display commits that exist\n>> diff --git a/revision.c b/revision.c\n>> index 5bc96444b6..51dbe21847 100644\n>> --- a/revision.c\n>> +++ b/revision.c\n>> @@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n>>  \t\trevs->simplify_by_decoration = 1;\n>>  \t\trevs->limited = 1;\n>>  \t\trevs->prune = 1;\n>> +\t} else if (!strcmp(arg, \"--simplify-forks\")) {\n>> +\t\trevs->limited = 1;\n>> +\t\trevs->simplify_forks = 1;\n>\n> I recommend dropping the revs->limited setting here and instead fixing the\n> performance instead. But maybe that should be a second patch on top of this\n> one.\n\n(See above.)\n\n>>  \t} else if (!strcmp(arg, \"--date-order\")) {\n>>  \t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n>>  \t\trevs->topo_order = 1;\n>> @@ -3095,6 +3098,63 @@ static void simplify_merges(struct rev_info *revs)\n>>  \t}\n>>  }\n>>\n>> +static void simplify_forks(struct rev_info *revs)\n>> +{\n>> +\tstruct commit_list *stack, *list_lr, *iter_list;\n>> +\tstruct commit_list **parents;\n>\n> You want \"struct commit_list *parents\" here for simpler use.\n\nUsing a pointer to the pointer makes the amputation of the parents much\nmore uniform: we can just pop_commit(parents), and it handles the cases\nof the first parent (which is addressed by commit->parents) and later\nparents (which are addressed by list_element->next).\n\nOf course, I'm insistent here that we should still be amputating the\ngraph.\n\n>> +\tstruct commit *commit, *parent;\n>> +\n>> +\tstack = NULL;\n>> +\tlist_lr = NULL;\n>> +\n>> +\tclear_object_flags(SIMP_FORK_VISITED);\n>> +\n>> +\tfor(iter_list = revs->commits; iter_list; iter_list = iter_list->next) {\n>\n> This method could use a split into at least two. I count three levels of nested\n> loops here, so please break them up into smaller methods.\n\n(see revision 3).\n\n>> +\t\t/* process every commit to be displayed exactly once */\n>> +\t\tif(iter_list->item->object.flags & SIMP_FORK_VISITED)\n>> +\t\t\tcontinue;\n>> +\t\tclear_object_flags(SIMP_FORK_VISITING);\n>\n> This drops the flag from all commits. This will cause quadratic performance\n> if combined with \"--all\". Drop this and instead clear the flag yourself as you\n> visit commits.\n\nSee revision 3.  I now re-walk the tree as needed.  Performance under\n--all is now extremely good (but does not stream).\n\n>> +\t\tcommit_list_insert(iter_list->item, &stack);\n>> +\t\titer_list->item->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING;\n>> +\t\twhile(stack) {\n>> +\t\t\tcommit = pop_commit(&stack);\n>> +\t\t\t/* process the parent nodes: removing links to\n>> +\t\t\t * commits already visited (creating a spanning tree)\n>> +\t\t\t */\n>> +\t\t\tparents = &(commit->parents);\n>> +\t\t\twhile(*parents) {\n>\n> You have some whitespace issues. Put a space between \"while\" and \"(\". Same with \"if\"s below.\n\n(See revision 3).  I think I got them all.\n\n>> +\t\t\t\tparent = (*parents)->item;\n>> +\t\t\t\tif(parent->object.flags & SIMP_FORK_VISITING) {\n>> +\t\t\t\t\t/* We have already visited this commit, from the same root.\n>> +\t\t\t\t\t * We do not explore it at all.\n>> +\t\t\t\t\t */\n>> +\t\t\t\t\tpop_commit(parents);\n>\n> I don't think you want pop_commit() here. You want to have \"parents = parents->next\" at the end.\n>\n> Now, if this is how you are \"simplifying\" the edges in the final output, then I think this is\n> destructive and unsafe! You are literally modifying \"commit->parents\" so if another operation in\n> Git tries to read those parents it will see the wrong data.\n>\n> Think about a different way to achieve your goal here, perhaps in the rendering portion of\n> graph.c instead of here.\n\nI would really like to be blissfully ignorant of branches' merge bases.\n\nI understand that this feature interacts nontrivially with things like\n--boundary (and in fact does retain significant information in the\nordering---see the last test case in t6016).  That said, it's not clear\nto me the use case for this when combined with other sophisticated graph\nmanipulations.\n\nAt the end of the day, I'm trying to make a feature that aids in\nvisualizing the repository.  Do you had an example case where someone\nwould like to use this feature, but removing these parents makes these\nother options less useful?\n\n>> +\t\t\t\t} else if(parent->object.flags & SIMP_FORK_VISITED) {\n>> +\t\t\t\t\t/* We visited this commit before, but from a different root.\n>> +\t\t\t\t\t * Leave it attached, but do not explore it further.\n>> +\t\t\t\t\t */\n>> +\t\t\t\t\tparents = &((*parents)->next);\n>> +\t\t\t\t} else {\n>> +\t\t\t\t\t/* We have not visited this commit yet. Explore it, as usual.\n>> +\t\t\t\t\t */\n>> +\t\t\t\t\tparent->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING;\n>> +\t\t\t\t\tcommit_list_insert(parent, &list_lr);\n>> +\t\t\t\t\tparents = &((*parents)->next);\n>> +\t\t\t\t}\n>\n> It is very unclear that your loop terminates. Instead, use\n> \"parents = parents->next\" at the end of the loop block to\n> make is extremely clear that the loop behaves as expected.\n>\n> Of course, this assumes that you are not being destructive\n> to the commit parents as you explore.\n\n(*parents) is a commit_list.  If, at the start of an iteration of the\nloop, it has n items in it, by the end of that iteration, we will have\neither removed the head commit (via pop_commit) or advanced one item\ndown the list.  In either case, there are n-1 items in the list at the\nend of the iteration.  Therefore, the loop must terminate.\n\nI've slightly adjusted the layout to make this more clear.\n\n>> +\t\t\t}\n>> +\n>> +\t\t\t/* feed the parents, right to left (reversed) onto the\n>> +\t\t\t * stack to do a depth-first traversal of the commit graph\n>> +\t\t\t */\n>\n> nit: multi-line comment style [1]\n>\n> [1] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L285-L291\n>\n>> +\t\t\twhile(list_lr) {\n>> +\t\t\t\tcommit_list_insert(pop_commit(&list_lr), &stack);\n>> +\t\t\t}\n>\n> nit: No curly braces around single-line blocks. [2]\n>\n> [2] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L239-L243\n\nThank you (and see revision 3).\n\n>> +\t\t}\n>> +\t}\n>> +\n>> +\tclear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING);\n>> +}\n>> +\n>>  static void set_children(struct rev_info *revs)\n>>  {\n>>  \tstruct commit_list *l;\n>> @@ -3392,6 +3452,8 @@ int prepare_revision_walk(struct rev_info *revs)\n>>  \tif (revs->limited) {\n>>  \t\tif (limit_list(revs) < 0)\n>>  \t\t\treturn -1;\n>> +\t\tif (revs->simplify_forks)\n>> +\t\t\tsimplify_forks(revs);\n>>  \t\tif (revs->topo_order)\n>>  \t\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n>>  \t} else if (revs->topo_order)\n>> diff --git a/revision.h b/revision.h\n>> index c1af164b30..f1abdb26b0 100644\n>> --- a/revision.h\n>> +++ b/revision.h\n>> @@ -51,6 +51,11 @@\n>>  #define TOPO_WALK_EXPLORED\t(1u<<27)\n>>  #define TOPO_WALK_INDEGREE\t(1u<<28)\n>>\n>> +/* Re-use the TOPO_WALK flagspace for simplify_forks\n>> + */\n>> +#define SIMP_FORK_VISITED\t(1u<<27)\n>> +#define SIMP_FORK_VISITING\t(1u<<28)\n>\n> I don't like that you are re-using these, as it is dangerous for later\n> collisions. At the moment, these flags are not used in the same code paths\n> because you specify \"limited = 1\" and that code path does not use TOPO_WALK_*\n> macros.\n\nI'm happy to use a different bit, and it would make me sleep easier\nknowing that this code is portable without worrying about this flag.\nI'm now using bits 23 and 24.\n\n>>  #define DECORATE_SHORT_REFS\t1\n>>  #define DECORATE_FULL_REFS\t2\n>>\n>> @@ -132,6 +137,7 @@ struct rev_info {\n>>  \t\t\tno_walk:2,\n>>  \t\t\tremove_empty_trees:1,\n>>  \t\t\tsimplify_history:1,\n>> +\t\t\tsimplify_forks:1,\n>>  \t\t\tshow_pulls:1,\n>>  \t\t\ttopo_order:1,\n>>  \t\t\tsimplify_merges:1,\n>> diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh\n>> index f5e6e92f5b..d99214b6df 100755\n>> --- a/t/t6016-rev-list-graph-simplify-history.sh\n>> +++ b/t/t6016-rev-list-graph-simplify-history.sh\n>> @@ -85,6 +85,28 @@ test_expect_success '--graph --all' '\n>>  \ttest_cmp expected actual\n>>  \t'\n>>\n>> +# Make sure that simplify_histpry_forks produces a spanning tree\n>> +test_expect_success '--graph --simplify-forks --all' '\n>> +\trm -f expected &&\n>> +\techo \"* $A7\" >> expected &&\n>> +\techo \"*   $A6\" >> expected &&\n>> +\techo \"|\\  \" >> expected &&\n>> +\techo \"| * $C4\" >> expected &&\n>> +\techo \"| * $C3\" >> expected &&\n>> +\techo \"* $A5\" >> expected &&\n>> +\techo \"*-.   $A4\" >> expected &&\n>> +\techo \"|\\ \\  \" >> expected &&\n>> +\techo \"| | * $C2\" >> expected &&\n>> +\techo \"| | * $C1\" >> expected &&\n>> +\techo \"| * $B2\" >> expected &&\n>> +\techo \"| * $B1\" >> expected &&\n>> +\techo \"* $A3\" >> expected &&\n>> +\techo \"* $A2\" >> expected &&\n>> +\techo \"* $A1\" >> expected &&\n>\n> Do not use too many echos like this. Instead use t4215-log-skewed-merges.sh\n> as an example [3].\n>\n> [3] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/t/t4215-log-skewed-merges.sh#L24-L37\n>\n> I also hope that you can find more complicated cases to\n> test, including:\n>\n>  1. A merge that brings in a merge (think a feature branch)\n>  2. A merge that brings in a twisted merge (think a user using \"git pull\").\n>\n> Here are some example --graph and --simplify-forks outputs to try. I\n> have not tested these myself, but I believe they are interesting test\n> cases that can trip up other algorithms.\n>\n> Merge bringing a merge (non-twisted):\n>\n>  --graph\t--simplify-forks\n>  *\t\t*\n>  |\\\t\t|\\\n>  | *\t\t| *\n>  | |\\\t\t| |\\\n>  | | *\t\t| | *\n>  | * |\t\t| *\n>  * | |\t\t*\n>  |/ /\t\t*\n>  * /\t\t*\n>  |/\n>  *\n>\n> Twisted merge:\n>\n>  --graph\t--simplify-forks\n>  *\t\t*\n>  |\\\t\t|\\\n>  | *\t\t| *\n>  | |\\\t\t| *\n>  | * |\t\t*\n>  | | |\t\t*\n>  * |/\t\t*\n>  |/|\n>  * |\n>  |/\n>  *\n\nThat is much nicer.  I've cleaned up t6106 in a similar way, and test\n--ignore-merge-bases there, t4215, and in the new t4216.\n\nThanks,\nAntonio\n"},{"id":"396748","messageId":"3a2605b6-c612-f70c-a11e-1e1cc3f59184@gmail.com","threadId":"53330","inReplyTo":"d3079ba8-33e1-3b68-23d2-ea97b9ca1e97@gmail.com","subject":"[PATCH 1/3 v3] Clean up t6016-rev-list-graph-simplify-history","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-05-01T14:21:04Z","receivedAt":"2020-05-01T14:21:08Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"Simplifies the logic used to test rev-list, making adding new tests\neasier.  Uses a heredoc and postprocessing of the rev-list output\ninstead of shell substitutions and manually escaped echo's.\n\nSigned-off-by: Antonio Russo <antonio.e.russo@gmail.com>\n---\n t/t6016-rev-list-graph-simplify-history.sh | 349 ++++++++++-----------\n 1 file changed, 166 insertions(+), 183 deletions(-)\n\ndiff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh\nindex f5e6e92f5b..eac271a4fa 100755\n--- a/t/t6016-rev-list-graph-simplify-history.sh\n+++ b/t/t6016-rev-list-graph-simplify-history.sh\n@@ -9,6 +9,12 @@ test_description='--graph and simplified history'\n\n . ./test-lib.sh\n\n+check_graph () {\n+\tcat >expected &&\n+\tgit rev-list --graph \"$@\" | sed \"$(cat sedscript)\" > actual &&\n+\ttest_cmp expected actual\n+}\n+\n test_expect_success 'set up rev-list --graph test' '\n \t# 3 commits on branch A\n \ttest_commit A1 foo.txt &&\n@@ -43,76 +49,62 @@ test_expect_success 'set up rev-list --graph test' '\n\n \ttest_commit A7 bar.txt &&\n\n-\t# Store commit names in variables for later use\n-\tA1=$(git rev-parse --verify A1) &&\n-\tA2=$(git rev-parse --verify A2) &&\n-\tA3=$(git rev-parse --verify A3) &&\n-\tA4=$(git rev-parse --verify A4) &&\n-\tA5=$(git rev-parse --verify A5) &&\n-\tA6=$(git rev-parse --verify A6) &&\n-\tA7=$(git rev-parse --verify A7) &&\n-\tB1=$(git rev-parse --verify B1) &&\n-\tB2=$(git rev-parse --verify B2) &&\n-\tC1=$(git rev-parse --verify C1) &&\n-\tC2=$(git rev-parse --verify C2) &&\n-\tC3=$(git rev-parse --verify C3) &&\n-\tC4=$(git rev-parse --verify C4)\n-\t'\n+\techo \"s/ *$//;\" > sedscript &&\n+\t( for tag in $(git tag -l) ; do echo \"s/$(git rev-parse --verify $tag)/$tag/;\" >> sedscript ; done )\n+'\n\n test_expect_success '--graph --all' '\n-\trm -f expected &&\n-\techo \"* $A7\" >> expected &&\n-\techo \"*   $A6\" >> expected &&\n-\techo \"|\\\\  \" >> expected &&\n-\techo \"| * $C4\" >> expected &&\n-\techo \"| * $C3\" >> expected &&\n-\techo \"* | $A5\" >> expected &&\n-\techo \"| |   \" >> expected &&\n-\techo \"|  \\\\  \" >> expected &&\n-\techo \"*-. | $A4\" >> expected &&\n-\techo \"|\\\\ \\\\| \" >> expected &&\n-\techo \"| | * $C2\" >> expected &&\n-\techo \"| | * $C1\" >> expected &&\n-\techo \"| * | $B2\" >> expected &&\n-\techo \"| * | $B1\" >> expected &&\n-\techo \"* | | $A3\" >> expected &&\n-\techo \"| |/  \" >> expected &&\n-\techo \"|/|   \" >> expected &&\n-\techo \"* | $A2\" >> expected &&\n-\techo \"|/  \" >> expected &&\n-\techo \"* $A1\" >> expected &&\n-\tgit rev-list --graph --all > actual &&\n-\ttest_cmp expected actual\n-\t'\n+\tcheck_graph --all <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t| * C3\n+\t* | A5\n+\t| |\n+\t|  \\\n+\t*-. | A4\n+\t|\\ \\|\n+\t| | * C2\n+\t| | * C1\n+\t| * | B2\n+\t| * | B1\n+\t* | | A3\n+\t| |/\n+\t|/|\n+\t* | A2\n+\t|/\n+\t* A1\n+\tEOF\n+'\n\n # Make sure the graph_is_interesting() code still realizes\n # that undecorated merges are interesting, even with --simplify-by-decoration\n test_expect_success '--graph --simplify-by-decoration' '\n-\trm -f expected &&\n \tgit tag -d A4 &&\n-\techo \"* $A7\" >> expected &&\n-\techo \"*   $A6\" >> expected &&\n-\techo \"|\\\\  \" >> expected &&\n-\techo \"| * $C4\" >> expected &&\n-\techo \"| * $C3\" >> expected &&\n-\techo \"* | $A5\" >> expected &&\n-\techo \"| |   \" >> expected &&\n-\techo \"|  \\\\  \" >> expected &&\n-\techo \"*-. | $A4\" >> expected &&\n-\techo \"|\\\\ \\\\| \" >> expected &&\n-\techo \"| | * $C2\" >> expected &&\n-\techo \"| | * $C1\" >> expected &&\n-\techo \"| * | $B2\" >> expected &&\n-\techo \"| * | $B1\" >> expected &&\n-\techo \"* | | $A3\" >> expected &&\n-\techo \"| |/  \" >> expected &&\n-\techo \"|/|   \" >> expected &&\n-\techo \"* | $A2\" >> expected &&\n-\techo \"|/  \" >> expected &&\n-\techo \"* $A1\" >> expected &&\n-\tgit rev-list --graph --all --simplify-by-decoration > actual &&\n-\ttest_cmp expected actual\n-\t'\n+\tcheck_graph --all --simplify-by-decoration <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t| * C3\n+\t* | A5\n+\t| |\n+\t|  \\\n+\t*-. | A4\n+\t|\\ \\|\n+\t| | * C2\n+\t| | * C1\n+\t| * | B2\n+\t| * | B1\n+\t* | | A3\n+\t| |/\n+\t|/|\n+\t* | A2\n+\t|/\n+\t* A1\n+\tEOF\n+'\n\n test_expect_success 'setup: get rid of decorations on B' '\n \tgit tag -d B2 &&\n@@ -122,142 +114,133 @@ test_expect_success 'setup: get rid of decorations on B' '\n\n # Graph with branch B simplified away\n test_expect_success '--graph --simplify-by-decoration prune branch B' '\n-\trm -f expected &&\n-\techo \"* $A7\" >> expected &&\n-\techo \"*   $A6\" >> expected &&\n-\techo \"|\\\\  \" >> expected &&\n-\techo \"| * $C4\" >> expected &&\n-\techo \"| * $C3\" >> expected &&\n-\techo \"* | $A5\" >> expected &&\n-\techo \"* | $A4\" >> expected &&\n-\techo \"|\\\\| \" >> expected &&\n-\techo \"| * $C2\" >> expected &&\n-\techo \"| * $C1\" >> expected &&\n-\techo \"* | $A3\" >> expected &&\n-\techo \"|/  \" >> expected &&\n-\techo \"* $A2\" >> expected &&\n-\techo \"* $A1\" >> expected &&\n-\tgit rev-list --graph --simplify-by-decoration --all > actual &&\n-\ttest_cmp expected actual\n-\t'\n+\tcheck_graph --simplify-by-decoration --all <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t| * C3\n+\t* | A5\n+\t* | A4\n+\t|\\|\n+\t| * C2\n+\t| * C1\n+\t* | A3\n+\t|/\n+\t* A2\n+\t* A1\n+\tEOF\n+'\n\n test_expect_success '--graph --full-history -- bar.txt' '\n-\trm -f expected &&\n-\techo \"* $A7\" >> expected &&\n-\techo \"*   $A6\" >> expected &&\n-\techo \"|\\\\  \" >> expected &&\n-\techo \"| * $C4\" >> expected &&\n-\techo \"* | $A5\" >> expected &&\n-\techo \"* | $A4\" >> expected &&\n-\techo \"|\\\\| \" >> expected &&\n-\techo \"* | $A3\" >> expected &&\n-\techo \"|/  \" >> expected &&\n-\techo \"* $A2\" >> expected &&\n-\tgit rev-list --graph --full-history --all -- bar.txt > actual &&\n-\ttest_cmp expected actual\n-\t'\n+\tcheck_graph --full-history --all -- bar.txt <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t* | A5\n+\t* | A4\n+\t|\\|\n+\t* | A3\n+\t|/\n+\t* A2\n+\tEOF\n+'\n\n test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '\n-\trm -f expected &&\n-\techo \"* $A7\" >> expected &&\n-\techo \"*   $A6\" >> expected &&\n-\techo \"|\\\\  \" >> expected &&\n-\techo \"| * $C4\" >> expected &&\n-\techo \"* | $A5\" >> expected &&\n-\techo \"* | $A3\" >> expected &&\n-\techo \"|/  \" >> expected &&\n-\techo \"* $A2\" >> expected &&\n-\tgit rev-list --graph --full-history --simplify-merges --all \\\n-\t\t-- bar.txt > actual &&\n-\ttest_cmp expected actual\n-\t'\n+\tcheck_graph --full-history --simplify-merges --all -- bar.txt <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t* | A5\n+\t* | A3\n+\t|/\n+\t* A2\n+\tEOF\n+'\n\n test_expect_success '--graph -- bar.txt' '\n-\trm -f expected &&\n-\techo \"* $A7\" >> expected &&\n-\techo \"* $A5\" >> expected &&\n-\techo \"* $A3\" >> expected &&\n-\techo \"| * $C4\" >> expected &&\n-\techo \"|/  \" >> expected &&\n-\techo \"* $A2\" >> expected &&\n-\tgit rev-list --graph --all -- bar.txt > actual &&\n-\ttest_cmp expected actual\n-\t'\n+\tcheck_graph --all -- bar.txt <<-\\EOF\n+\t* A7\n+\t* A5\n+\t* A3\n+\t| * C4\n+\t|/\n+\t* A2\n+\tEOF\n+'\n\n test_expect_success '--graph --sparse -- bar.txt' '\n-\trm -f expected &&\n-\techo \"* $A7\" >> expected &&\n-\techo \"* $A6\" >> expected &&\n-\techo \"* $A5\" >> expected &&\n-\techo \"* $A4\" >> expected &&\n-\techo \"* $A3\" >> expected &&\n-\techo \"| * $C4\" >> expected &&\n-\techo \"| * $C3\" >> expected &&\n-\techo \"| * $C2\" >> expected &&\n-\techo \"| * $C1\" >> expected &&\n-\techo \"|/  \" >> expected &&\n-\techo \"* $A2\" >> expected &&\n-\techo \"* $A1\" >> expected &&\n-\tgit rev-list --graph --sparse --all -- bar.txt > actual &&\n-\ttest_cmp expected actual\n-\t'\n+\tcheck_graph --sparse --all -- bar.txt <<-\\EOF\n+\t* A7\n+\t* A6\n+\t* A5\n+\t* A4\n+\t* A3\n+\t| * C4\n+\t| * C3\n+\t| * C2\n+\t| * C1\n+\t|/\n+\t* A2\n+\t* A1\n+\tEOF\n+'\n\n test_expect_success '--graph ^C4' '\n-\trm -f expected &&\n-\techo \"* $A7\" >> expected &&\n-\techo \"* $A6\" >> expected &&\n-\techo \"* $A5\" >> expected &&\n-\techo \"*   $A4\" >> expected &&\n-\techo \"|\\\\  \" >> expected &&\n-\techo \"| * $B2\" >> expected &&\n-\techo \"| * $B1\" >> expected &&\n-\techo \"* $A3\" >> expected &&\n-\tgit rev-list --graph --all ^C4 > actual &&\n-\ttest_cmp expected actual\n-\t'\n+\tcheck_graph --all ^C4 <<-\\EOF\n+\t* A7\n+\t* A6\n+\t* A5\n+\t*   A4\n+\t|\\\n+\t| * B2\n+\t| * B1\n+\t* A3\n+\tEOF\n+'\n\n test_expect_success '--graph ^C3' '\n-\trm -f expected &&\n-\techo \"* $A7\" >> expected &&\n-\techo \"*   $A6\" >> expected &&\n-\techo \"|\\\\  \" >> expected &&\n-\techo \"| * $C4\" >> expected &&\n-\techo \"* $A5\" >> expected &&\n-\techo \"*   $A4\" >> expected &&\n-\techo \"|\\\\  \" >> expected &&\n-\techo \"| * $B2\" >> expected &&\n-\techo \"| * $B1\" >> expected &&\n-\techo \"* $A3\" >> expected &&\n-\tgit rev-list --graph --all ^C3 > actual &&\n-\ttest_cmp expected actual\n-\t'\n+\tcheck_graph --all ^C3 <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t* A5\n+\t*   A4\n+\t|\\\n+\t| * B2\n+\t| * B1\n+\t* A3\n+\tEOF\n+'\n\n # I don't think the ordering of the boundary commits is really\n # that important, but this test depends on it.  If the ordering ever changes\n # in the code, we'll need to update this test.\n test_expect_success '--graph --boundary ^C3' '\n-\trm -f expected &&\n-\techo \"* $A7\" >> expected &&\n-\techo \"*   $A6\" >> expected &&\n-\techo \"|\\\\  \" >> expected &&\n-\techo \"| * $C4\" >> expected &&\n-\techo \"* | $A5\" >> expected &&\n-\techo \"| |     \" >> expected &&\n-\techo \"|  \\\\    \" >> expected &&\n-\techo \"*-. \\\\   $A4\" >> expected &&\n-\techo \"|\\\\ \\\\ \\\\  \" >> expected &&\n-\techo \"| * | | $B2\" >> expected &&\n-\techo \"| * | | $B1\" >> expected &&\n-\techo \"* | | | $A3\" >> expected &&\n-\techo \"o | | | $A2\" >> expected &&\n-\techo \"|/ / /  \" >> expected &&\n-\techo \"o / / $A1\" >> expected &&\n-\techo \" / /  \" >> expected &&\n-\techo \"| o $C3\" >> expected &&\n-\techo \"|/  \" >> expected &&\n-\techo \"o $C2\" >> expected &&\n-\tgit rev-list --graph --boundary --all ^C3 > actual &&\n-\ttest_cmp expected actual\n-\t'\n+\tcheck_graph --boundary --all ^C3 <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t* | A5\n+\t| |\n+\t|  \\\n+\t*-. \\   A4\n+\t|\\ \\ \\\n+\t| * | | B2\n+\t| * | | B1\n+\t* | | | A3\n+\to | | | A2\n+\t|/ / /\n+\to / / A1\n+\t / /\n+\t| o C3\n+\t|/\n+\to C2\n+\tEOF\n+'\n\n test_done\n-- \n2.26.2\n\n"},{"id":"396749","messageId":"1716d20d-6f0d-3872-cf36-6fc8d7bdb457@gmail.com","threadId":"53330","inReplyTo":"d3079ba8-33e1-3b68-23d2-ea97b9ca1e97@gmail.com","subject":"[PATCH 2/3 v3] Teach git-rev-list --ignore-merge-bases","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-05-01T14:22:27Z","receivedAt":"2020-05-01T14:22:31Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"This new option simplifies the graph of commits for merges.  Commits are\nshown before their parents, but edges from those commits to commits\nreachable from the first parent are removed.  Being disconnected from\nthe branch from which they were forked, these amputated merges\neffectively lose all information about their merge base.\n\nWhen used with --graph, this amputation can dramatically reduce the\nwidth of the displayed graph and the total time taken to draw all\noutput.\n\nThe implementation traverses all reachable commits with a\ndepth-first-search to produce a spanning tree.\n\nSigned-off-by: Antonio Russo <antonio.e.russo@gmail.com>\n---\n Documentation/rev-list-options.txt |  9 ++++\n object.h                           |  2 +-\n revision.c                         | 85 ++++++++++++++++++++++++++++++\n revision.h                         |  5 ++\n 4 files changed, 100 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 04ad7dd36e..3f5d196985 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -363,6 +363,15 @@ Default mode::\n \tmerges from the resulting history, as there are no selected\n \tcommits contributing to this merge.\n\n+--ignore-merge-bases::\n+\tShow commits that are introduced by each merge before showing\n+\tthe first parent of the merge but remove edges from those commits\n+\tto commits reachable from the first parent. When used with\n+\t`--graph`, this can help visualize repositories with many merges\n+\twhen you are not interested in the merge base used for each\n+\tmerge. It also reduces the width of the graph visualization\n+\twhen used with `--graph`.\n+\n --ancestry-path::\n \tWhen given a range of commits to display (e.g. 'commit1..commit2'\n \tor 'commit2 {caret}commit1'), only display commits that exist\ndiff --git a/object.h b/object.h\nindex b22328b838..0bf6fb0d55 100644\n--- a/object.h\n+++ b/object.h\n@@ -59,7 +59,7 @@ struct object_array {\n\n /*\n  * object flag allocation:\n- * revision.h:               0---------10         15                   25----28\n+ * revision.h:               0---------10         15                   23----28\n  * fetch-pack.c:             01\n  * negotiator/default.c:       2--5\n  * walker.c:                 0-2\ndiff --git a/revision.c b/revision.c\nindex 5bc96444b6..ae81175e34 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->simplify_by_decoration = 1;\n \t\trevs->limited = 1;\n \t\trevs->prune = 1;\n+\t} else if (!strcmp(arg, \"--ignore-merge-bases\")) {\n+\t\trevs->limited = 1;\n+\t\trevs->ignore_merge_bases = 1;\n \t} else if (!strcmp(arg, \"--date-order\")) {\n \t\trevs->sort_order = REV_SORT_BY_COMMIT_DATE;\n \t\trevs->topo_order = 1;\n@@ -3095,6 +3098,86 @@ static void simplify_merges(struct rev_info *revs)\n \t}\n }\n\n+static void cleanup_ignore_merge_bases(struct commit *commit) {\n+\tstruct commit_list *stack;\n+\tstruct commit_list *parents;\n+\tstack = NULL;\n+\n+\tcommit_list_insert(commit, &stack);\n+\twhile (stack) {\n+\t\tcommit = pop_commit(&stack);\n+\t\tcommit->object.flags &= !IGN_MRG_BASES_VISITING;\n+\n+\t\tparents = commit->parents;\n+\t\tfor (parents = commit->parents; parents; parents = parents->next)\n+\t\t\tcommit_list_insert(parents->item, &stack);\n+\t}\n+}\n+\n+static void do_ignore_merge_bases(struct commit *commit) {\n+\tstruct commit_list *stack, *list_lr;\n+\tstruct commit_list **parents;\n+\tstruct commit *parent;\n+\tstack = NULL;\n+\tlist_lr = NULL;\n+\n+\t/* process every commit to be displayed exactly once */\n+\tcommit_list_insert(commit, &stack);\n+\tcommit->object.flags |= IGN_MRG_BASES_VISITED | IGN_MRG_BASES_VISITING;\n+\twhile (stack) {\n+\t\tcommit = pop_commit(&stack);\n+\t\t/*\n+\t\t * process the parent nodes: removing links to\n+\t\t * commits already visited (creating a spanning tree)\n+\t\t */\n+\t\tparents = &(commit->parents);\n+\t\twhile (*parents) {\n+\t\t\tparent = (*parents)->item;\n+\t\t\tif (parent->object.flags & IGN_MRG_BASES_VISITING) {\n+\t\t\t\t/*\n+\t\t\t\t * We have already visited this commit, from the same root.\n+\t\t\t\t * We do not explore it at all.\n+\t\t\t\t */\n+\t\t\t\tpop_commit(parents);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (!(parent->object.flags & IGN_MRG_BASES_VISITED)) {\n+\t\t\t\t/*\n+\t\t\t\t * If we visited this commit before, but from a different root,\n+\t\t\t\t * leave it attached, but do not explore it further.\n+\t\t\t\t *\n+\t\t\t\t * If we have not visited this commit yet, explore it, as usual.\n+\t\t\t\t */\n+\t\t\t\tparent->object.flags |= IGN_MRG_BASES_VISITED | IGN_MRG_BASES_VISITING;\n+\t\t\t\tcommit_list_insert(parent, &list_lr);\n+\t\t\t}\n+\t\t\tparents = &((*parents)->next);\n+\t\t}\n+\n+\t\t/*\n+\t\t * Feed the parents, right to left (reversed) onto the\n+\t\t * stack to do a depth-first traversal of the commit graph.\n+\t\t */\n+\t\twhile (list_lr)\n+\t\t\tcommit_list_insert(pop_commit(&list_lr), &stack);\n+\t}\n+}\n+\n+static void ignore_merge_bases(struct rev_info *revs)\n+{\n+\tstruct commit_list *iter_list;\n+\tstruct commit *prev = NULL;\n+\n+\tfor (iter_list = revs->commits; iter_list; iter_list = iter_list->next) {\n+\t\tif (iter_list->item->object.flags & IGN_MRG_BASES_VISITED)\n+\t\t\tcontinue;\n+\t\tif (prev)\n+\t\t\tcleanup_ignore_merge_bases(prev);\n+\t\tprev = iter_list->item;\n+\t\tdo_ignore_merge_bases(prev);\n+\t}\n+}\n+\n static void set_children(struct rev_info *revs)\n {\n \tstruct commit_list *l;\n@@ -3392,6 +3475,8 @@ int prepare_revision_walk(struct rev_info *revs)\n \tif (revs->limited) {\n \t\tif (limit_list(revs) < 0)\n \t\t\treturn -1;\n+\t\tif (revs->ignore_merge_bases)\n+\t\t\tignore_merge_bases(revs);\n \t\tif (revs->topo_order)\n \t\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n \t} else if (revs->topo_order)\ndiff --git a/revision.h b/revision.h\nindex c1af164b30..93b318b304 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -37,6 +37,10 @@\n\n /* WARNING: This is also used as REACHABLE in commit-graph.c. */\n #define PULL_MERGE\t(1u<<15)\n+\n+#define IGN_MRG_BASES_VISITED\t(1u<<23)\n+#define IGN_MRG_BASES_VISITING\t(1u<<24)\n+\n /*\n  * Indicates object was reached by traversal. i.e. not given by user on\n  * command-line or stdin.\n@@ -132,6 +136,7 @@ struct rev_info {\n \t\t\tno_walk:2,\n \t\t\tremove_empty_trees:1,\n \t\t\tsimplify_history:1,\n+\t\t\tignore_merge_bases:1,\n \t\t\tshow_pulls:1,\n \t\t\ttopo_order:1,\n \t\t\tsimplify_merges:1,\n-- \n2.26.2\n\n"},{"id":"396750","messageId":"c8fb7235-1dd4-ff2c-bae4-0fb83187c155@gmail.com","threadId":"53330","inReplyTo":"d3079ba8-33e1-3b68-23d2-ea97b9ca1e97@gmail.com","subject":"[PATCH 3/3 v3] Add new tests of ignore-merge-bases","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-05-01T14:23:07Z","receivedAt":"2020-05-01T14:23:11Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"Extend t4215 and t6016 to also use --ignore-merge-bases on their test\ncases.\n\nAdd the new test case t4216-log-merges, with three tests: a standard\nfeature merge, a \"twisted\" feature merge, and the motivating case for\nignore-merge-bases: a \"mountain\" of merges.\n\nSigned-off-by: Antonio Russo <antonio.e.russo@gmail.com>\n---\n t/t4215-log-skewed-merges.sh               | 165 +++++++++++++\n t/t4216-log-merges.sh                      | 273 +++++++++++++++++++++\n t/t6016-rev-list-graph-simplify-history.sh |  69 ++++++\n 3 files changed, 507 insertions(+)\n create mode 100755 t/t4216-log-merges.sh\n\ndiff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh\nindex 28d0779a8c..fb5df1a323 100755\n--- a/t/t4215-log-skewed-merges.sh\n+++ b/t/t4215-log-skewed-merges.sh\n@@ -38,6 +38,22 @@ test_expect_success 'log --graph with merge fusing with its left and right neigh\n \tEOF\n '\n\n+test_expect_success 'log --graph with merge fusing with its left and right neighbors (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases <<-\\EOF\n+\t*   H\n+\t|\\\n+\t| *   G\n+\t| |\\\n+\t| | * F\n+\t| *   E\n+\t| |\\\n+\t| | * D\n+\t| * C\n+\t* B\n+\t* A\n+\tEOF\n+'\n+\n test_expect_success 'log --graph with left-skewed merge' '\n \tgit checkout --orphan 0_p && test_commit 0_A &&\n \tgit checkout -b 0_q 0_p && test_commit 0_B &&\n@@ -72,6 +88,20 @@ test_expect_success 'log --graph with left-skewed merge' '\n \tEOF\n '\n\n+test_expect_success 'log --graph with left-skewed merge (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases <<-\\EOF\n+\t*-----.   0_H\n+\t|\\ \\ \\ \\\n+\t| | | | * 0_G\n+\t| | | * 0_F\n+\t| | | * 0_E\n+\t| | * 0_D\n+\t| | * 0_C\n+\t| * 0_B\n+\t* 0_A\n+\tEOF\n+'\n+\n test_expect_success 'log --graph with nested left-skewed merge' '\n \tgit checkout --orphan 1_p &&\n \ttest_commit 1_A &&\n@@ -100,6 +130,21 @@ test_expect_success 'log --graph with nested left-skewed merge' '\n \tEOF\n '\n\n+test_expect_success 'log --graph with nested left-skewed merge (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases<<-\\EOF\n+\t*   1_H\n+\t|\\\n+\t| *   1_G\n+\t| |\\\n+\t| | * 1_F\n+\t| * 1_E\n+\t| * 1_D\n+\t* 1_C\n+\t* 1_B\n+\t* 1_A\n+\tEOF\n+'\n+\n test_expect_success 'log --graph with nested left-skewed merge following normal merge' '\n \tgit checkout --orphan 2_p &&\n \ttest_commit 2_A &&\n@@ -137,6 +182,23 @@ test_expect_success 'log --graph with nested left-skewed merge following normal\n \tEOF\n '\n\n+test_expect_success 'log --graph with nested left-skewed merge following normal merge (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases<<-\\EOF\n+\t*   2_K\n+\t|\\\n+\t| *   2_J\n+\t| |\\\n+\t| | * 2_H\n+\t| | * 2_G\n+\t| | * 2_F\n+\t| * 2_E\n+\t| * 2_D\n+\t* 2_C\n+\t* 2_B\n+\t* 2_A\n+\tEOF\n+'\n+\n test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge' '\n \tgit checkout --orphan 3_p &&\n \ttest_commit 3_A &&\n@@ -170,6 +232,23 @@ test_expect_success 'log --graph with nested right-skewed merge following left-s\n \tEOF\n '\n\n+test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases<<-\\EOF\n+\t*   3_J\n+\t|\\\n+\t| *   3_H\n+\t| |\\\n+\t| | * 3_G\n+\t| * 3_F\n+\t| *   3_E\n+\t| |\\\n+\t| | * 3_D\n+\t| * 3_C\n+\t| * 3_B\n+\t* 3_A\n+\tEOF\n+'\n+\n test_expect_success 'log --graph with right-skewed merge following a left-skewed one' '\n \tgit checkout --orphan 4_p &&\n \ttest_commit 4_A &&\n@@ -202,6 +281,23 @@ test_expect_success 'log --graph with right-skewed merge following a left-skewed\n \tEOF\n '\n\n+test_expect_success 'log --graph with right-skewed merge following a left-skewed one (ignore-merge-bases)' '\n+\tcheck_graph --date-order --ignore-merge-bases<<-\\EOF\n+\t*   4_H\n+\t|\\\n+\t| *   4_G\n+\t| |\\\n+\t| * | 4_F\n+\t| * |   4_E\n+\t| |\\ \\\n+\t| | * | 4_D\n+\t| |  /\n+\t| | * 4_C\n+\t| * 4_B\n+\t* 4_A\n+\tEOF\n+'\n+\n test_expect_success 'log --graph with octopus merge with column joining its penultimate parent' '\n \tgit checkout --orphan 5_p &&\n \ttest_commit 5_A &&\n@@ -239,6 +335,21 @@ test_expect_success 'log --graph with octopus merge with column joining its penu\n \tEOF\n '\n\n+test_expect_success 'log --graph with octopus merge with column joining its penultimate parent (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases<<-\\EOF\n+\t*   5_H\n+\t|\\\n+\t| *-.   5_G\n+\t| |\\ \\\n+\t| | | * 5_F\n+\t| | * 5_E\n+\t| | * 5_C\n+\t| * 5_B\n+\t* 5_D\n+\t* 5_A\n+\tEOF\n+'\n+\n test_expect_success 'log --graph with multiple tips' '\n \tgit checkout --orphan 6_1 &&\n \ttest_commit 6_A &&\n@@ -281,6 +392,27 @@ test_expect_success 'log --graph with multiple tips' '\n \tEOF\n '\n\n+test_expect_success 'log --graph with multiple tips (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases 6_1 6_3 6_5 <<-\\EOF\n+\t*   6_I\n+\t|\\\n+\t| | *   6_H\n+\t| | |\\\n+\t| | | * 6_G\n+\t| | * 6_E\n+\t| | | * 6_F\n+\t| |_|/|\n+\t|/| |/\n+\t| |/|\n+\t| * | 6_D\n+\t|  /\n+\t* / 6_C\n+\t|/\n+\t* 6_B\n+\t* 6_A\n+\tEOF\n+'\n+\n test_expect_success 'log --graph with multiple tips and colors' '\n \ttest_config log.graphColors red,green,yellow,blue,magenta,cyan &&\n \tcat >expect.colors <<-\\EOF &&\n@@ -370,4 +502,37 @@ test_expect_success 'log --graph with multiple tips' '\n \tEOF\n '\n\n+test_expect_success 'log --graph with multiple tips (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases M_1 M_3 M_5 M_7 <<-\\EOF\n+\t*   7_M1\n+\t|\\\n+\t| | *   7_M2\n+\t| | |\\\n+\t| | | * 7_H\n+\t| | | | *   7_M3\n+\t| | | | |\\\n+\t| | | | | * 7_J\n+\t| | | | * | 7_I\n+\t| | | | * | 7_A\n+\t| | | |  /\n+\t| | | | | *   7_M4\n+\t| |_|_|_|/|\\\n+\t|/| | | |/ /\n+\t| | |_|/| /\n+\t| |/| | |/\n+\t| | | |/|\n+\t| | |/| |\n+\t| | * | | 7_G\n+\t| | | |/\n+\t| | |/|\n+\t| | * | 7_F\n+\t| |  /\n+\t| * / 7_E\n+\t| |/\n+\t| * 7_D\n+\t* 7_C\n+\t* 7_B\n+\tEOF\n+'\n+\n test_done\ndiff --git a/t/t4216-log-merges.sh b/t/t4216-log-merges.sh\nnew file mode 100755\nindex 0000000000..84b1973131\n--- /dev/null\n+++ b/t/t4216-log-merges.sh\n@@ -0,0 +1,273 @@\n+#!/bin/sh\n+\n+test_description='git log --graph of merges'\n+\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/lib-log-graph.sh\n+\n+check_graph () {\n+\tcat >expect &&\n+\tlib_test_cmp_graph --format=%s \"$@\"\n+}\n+\n+test_expect_success 'log --graph with merge pulling in a feature' '\n+\tgit checkout --orphan _p && test_commit A &&\n+\tgit checkout -b _q &&\n+\tgit checkout _p && test_commit B &&\n+\tgit checkout -b _r &&\n+\tgit checkout _p && test_commit C &&\n+\tgit checkout _r && test_commit F_1 &&\n+\tgit checkout _q && test_commit F_2 &&\n+\tgit checkout _r && git merge --no-ff _q -m M &&\n+\tgit checkout _p && git merge --no-ff _r -m D &&\n+\n+\tcheck_graph <<-\\EOF\n+\t*   D\n+\t|\\\n+\t| *   M\n+\t| |\\\n+\t| | * F_2\n+\t| * | F_1\n+\t* | | C\n+\t|/ /\n+\t* / B\n+\t|/\n+\t* A\n+\tEOF\n+'\n+\n+test_expect_success 'log --graph with merge pulling in a feature (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases <<-\\EOF\n+\t*   D\n+\t|\\\n+\t| *   M\n+\t| |\\\n+\t| | * F_2\n+\t| * F_1\n+\t* C\n+\t* B\n+\t* A\n+\tEOF\n+'\n+\n+test_expect_success 'log --graph with twisted merge pulling in a feature from master' '\n+\tgit checkout --orphan 0_p && test_commit 0_A &&\n+\tgit checkout -b 0_q &&\n+\tgit checkout 0_p && test_commit 0_B &&\n+\tgit checkout -b 0_r &&\n+\tgit checkout 0_p && test_commit 0_C &&\n+\tgit checkout 0_q && test_commit 0_F1 && git merge --no-ff 0_r -m 0_M1 &&\n+\tgit checkout 0_p && git merge --no-ff 0_q -m 0_M2 &&\n+\n+\tcheck_graph <<-\\EOF\n+\t*   0_M2\n+\t|\\\n+\t| *   0_M1\n+\t| |\\\n+\t| * | 0_F1\n+\t* | | 0_C\n+\t| |/\n+\t|/|\n+\t* | 0_B\n+\t|/\n+\t* 0_A\n+\tEOF\n+'\n+\n+test_expect_success 'log --graph with twisted merge pulling in a feature from master (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases <<-\\EOF\n+\t*   0_M2\n+\t|\\\n+\t| * 0_M1\n+\t| * 0_F1\n+\t* 0_C\n+\t* 0_B\n+\t* 0_A\n+\tEOF\n+'\n+\n+test_expect_success 'log --graph with several merges' '\n+\tgit checkout --orphan 1_p &&\n+\ttest_commit 1_root &&\n+\tfor m in $(test_seq 1 10) ;\n+\tdo\n+\t\tgit checkout -b 1_f${m} 1_root ;\n+\t\ttest_commit 1_A${m} ;\n+\tdone &&\n+\tfor m in $(test_seq 1 10) ;\n+\tdo\n+\t\ti=$((11 - $m)) ;\n+\t\tgit merge --no-ff 1_f${i} -m 1_M${m}A${i} ;\n+\tdone &&\n+\tfor mp in $(test_seq 1 10) ;\n+\tdo\n+\t\tm=$((11 - mp))\n+\t\tgit checkout 1_f${m} ;\n+\t\ttest_commit 1_B${m} ;\n+\t\tgit checkout 1_p ;\n+\t\tgit merge --no-ff 1_f${m} -m 1_M${m} ;\n+\tdone &&\n+\n+\tcheck_graph <<-\\EOF\n+\t*   1_M1\n+\t|\\\n+\t| * 1_B1\n+\t* |   1_M2\n+\t|\\ \\\n+\t| * | 1_B2\n+\t* | |   1_M3\n+\t|\\ \\ \\\n+\t| * | | 1_B3\n+\t* | | |   1_M4\n+\t|\\ \\ \\ \\\n+\t| * | | | 1_B4\n+\t* | | | |   1_M5\n+\t|\\ \\ \\ \\ \\\n+\t| * | | | | 1_B5\n+\t* | | | | |   1_M6\n+\t|\\ \\ \\ \\ \\ \\\n+\t| * | | | | | 1_B6\n+\t* | | | | | |   1_M7\n+\t|\\ \\ \\ \\ \\ \\ \\\n+\t| * | | | | | | 1_B7\n+\t* | | | | | | |   1_M8\n+\t|\\ \\ \\ \\ \\ \\ \\ \\\n+\t| * | | | | | | | 1_B8\n+\t* | | | | | | | |   1_M9\n+\t|\\ \\ \\ \\ \\ \\ \\ \\ \\\n+\t| * | | | | | | | | 1_B9\n+\t* | | | | | | | | |   1_M10\n+\t|\\ \\ \\ \\ \\ \\ \\ \\ \\ \\\n+\t| * | | | | | | | | | 1_B10\n+\t| * | | | | | | | | |   1_M10A1\n+\t| |\\ \\ \\ \\ \\ \\ \\ \\ \\ \\\n+\t| | | |_|_|_|_|_|_|_|/\n+\t| | |/| | | | | | | |\n+\t| | * | | | | | | | | 1_A1\n+\t| |/ / / / / / / / /\n+\t|/| | | | | | | | |\n+\t| * | | | | | | | |   1_M9A2\n+\t| |\\ \\ \\ \\ \\ \\ \\ \\ \\\n+\t| | | |_|_|_|_|_|_|/\n+\t| | |/| | | | | | |\n+\t| | * | | | | | | | 1_A2\n+\t| |/ / / / / / / /\n+\t|/| | | | | | | |\n+\t| * | | | | | | |   1_M8A3\n+\t| |\\ \\ \\ \\ \\ \\ \\ \\\n+\t| | | |_|_|_|_|_|/\n+\t| | |/| | | | | |\n+\t| | * | | | | | | 1_A3\n+\t| |/ / / / / / /\n+\t|/| | | | | | |\n+\t| * | | | | | |   1_M7A4\n+\t| |\\ \\ \\ \\ \\ \\ \\\n+\t| | | |_|_|_|_|/\n+\t| | |/| | | | |\n+\t| | * | | | | | 1_A4\n+\t| |/ / / / / /\n+\t|/| | | | | |\n+\t| * | | | | |   1_M6A5\n+\t| |\\ \\ \\ \\ \\ \\\n+\t| | | |_|_|_|/\n+\t| | |/| | | |\n+\t| | * | | | | 1_A5\n+\t| |/ / / / /\n+\t|/| | | | |\n+\t| * | | | |   1_M5A6\n+\t| |\\ \\ \\ \\ \\\n+\t| | | |_|_|/\n+\t| | |/| | |\n+\t| | * | | | 1_A6\n+\t| |/ / / /\n+\t|/| | | |\n+\t| * | | |   1_M4A7\n+\t| |\\ \\ \\ \\\n+\t| | | |_|/\n+\t| | |/| |\n+\t| | * | | 1_A7\n+\t| |/ / /\n+\t|/| | |\n+\t| * | |   1_M3A8\n+\t| |\\ \\ \\\n+\t| | | |/\n+\t| | |/|\n+\t| | * | 1_A8\n+\t| |/ /\n+\t|/| |\n+\t| * | 1_M2A9\n+\t| |\\|\n+\t| | * 1_A9\n+\t| |/\n+\t|/|\n+\t| * 1_A10\n+\t|/\n+\t* 1_root\n+\tEOF\n+'\n+\n+test_expect_success 'log --graph with several merges (ignore-merge-bases)' '\n+\tcheck_graph --ignore-merge-bases <<-\\EOF\n+\t*   1_M1\n+\t|\\\n+\t| * 1_B1\n+\t*   1_M2\n+\t|\\\n+\t| * 1_B2\n+\t*   1_M3\n+\t|\\\n+\t| * 1_B3\n+\t*   1_M4\n+\t|\\\n+\t| * 1_B4\n+\t*   1_M5\n+\t|\\\n+\t| * 1_B5\n+\t*   1_M6\n+\t|\\\n+\t| * 1_B6\n+\t*   1_M7\n+\t|\\\n+\t| * 1_B7\n+\t*   1_M8\n+\t|\\\n+\t| * 1_B8\n+\t*   1_M9\n+\t|\\\n+\t| * 1_B9\n+\t*   1_M10\n+\t|\\\n+\t| * 1_B10\n+\t| *   1_M10A1\n+\t| |\\\n+\t| | * 1_A1\n+\t| *   1_M9A2\n+\t| |\\\n+\t| | * 1_A2\n+\t| *   1_M8A3\n+\t| |\\\n+\t| | * 1_A3\n+\t| *   1_M7A4\n+\t| |\\\n+\t| | * 1_A4\n+\t| *   1_M6A5\n+\t| |\\\n+\t| | * 1_A5\n+\t| *   1_M5A6\n+\t| |\\\n+\t| | * 1_A6\n+\t| *   1_M4A7\n+\t| |\\\n+\t| | * 1_A7\n+\t| *   1_M3A8\n+\t| |\\\n+\t| | * 1_A8\n+\t| *   1_M2A9\n+\t| |\\\n+\t| | * 1_A9\n+\t| * 1_A10\n+\t* 1_root\n+\tEOF\n+'\n+\n+test_done\ndiff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh\nindex eac271a4fa..a097be5ce5 100755\n--- a/t/t6016-rev-list-graph-simplify-history.sh\n+++ b/t/t6016-rev-list-graph-simplify-history.sh\n@@ -78,6 +78,27 @@ test_expect_success '--graph --all' '\n \tEOF\n '\n\n+# Make sure that ignore_merge_bases produces a spanning tree\n+test_expect_success '--graph --ignore-merge-bases --all' '\n+\tcheck_graph --ignore-merge-bases --all <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t| * C3\n+\t* A5\n+\t*-.   A4\n+\t|\\ \\\n+\t| | * C2\n+\t| | * C1\n+\t| * B2\n+\t| * B1\n+\t* A3\n+\t* A2\n+\t* A1\n+\tEOF\n+'\n+\n # Make sure the graph_is_interesting() code still realizes\n # that undecorated merges are interesting, even with --simplify-by-decoration\n test_expect_success '--graph --simplify-by-decoration' '\n@@ -147,6 +168,19 @@ test_expect_success '--graph --full-history -- bar.txt' '\n \tEOF\n '\n\n+test_expect_success '--graph --ignore-merge-bases --full-history -- bar.txt' '\n+\tcheck_graph --ignore-merge-bases --full-history --all -- bar.txt <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t* A5\n+\t* A4\n+\t* A3\n+\t* A2\n+\tEOF\n+'\n+\n test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '\n \tcheck_graph --full-history --simplify-merges --all -- bar.txt <<-\\EOF\n \t* A7\n@@ -160,6 +194,18 @@ test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '\n \tEOF\n '\n\n+test_expect_success '--graph --ignore-merge-bases --full-history --simplify-merges -- bar.txt' '\n+\tcheck_graph --ignore-merge-bases --full-history --simplify-merges --all -- bar.txt <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t* A5\n+\t* A3\n+\t* A2\n+\tEOF\n+'\n+\n test_expect_success '--graph -- bar.txt' '\n \tcheck_graph --all -- bar.txt <<-\\EOF\n \t* A7\n@@ -243,4 +289,27 @@ test_expect_success '--graph --boundary ^C3' '\n \tEOF\n '\n\n+test_expect_success '--graph --ignore-merge-bases --boundary ^C3' '\n+\tcheck_graph --ignore-merge-bases --boundary --all ^C3 <<-\\EOF\n+\t* A7\n+\t*   A6\n+\t|\\\n+\t| * C4\n+\t* | A5\n+\t| |\n+\t|  \\\n+\t*-. \\   A4\n+\t|\\ \\ \\\n+\t| * | | B2\n+\t| * | | B1\n+\t|  / /\n+\t* | | A3\n+\to | | A2\n+\t / /\n+\to / C2\n+\t /\n+\to C3\n+\tEOF\n+'\n+\n test_done\n-- \n2.26.2\n\n"},{"id":"396769","messageId":"7d85d901-714e-12c7-69fd-38f49c686440@gmail.com","threadId":"53330","inReplyTo":"2a668dd2-35c0-7510-fc4d-6c44e8407a07@gmail.com","subject":"Re: [PATCH v2] Teach git-rev-list --simplify-forks","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-05-01T15:44:43Z","receivedAt":"2020-05-01T15:44:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/1/2020 10:13 AM, Antonio Russo wrote:\n> On 4/29/20 7:12 AM, Derrick Stolee wrote:\n>> On 4/29/2020 4:01 AM, Antonio Russo wrote:\n>>> When used with --graph, instead of displaying the full graph, display a\n>>> spanning subgraph produced by a depth-first search of the graph visiting\n>>> parents from left to right.  Edges to already visited commits are\n>>> discarded.  This process is repeated for every commit to be displayed.\n>>>\n>>> This is valuable to reduce visual clutter when there are many merges\n>>> that were not rebased onto each other and the user is primarily\n>>> interested in the state of the branch being merged into.\n>>\n>> My earlier comment to recommend how to fix the test failures intended\n>> to demonstrate that this area of code requires a bit of precision. I\n>> took some time to review this patch, but I find it needs some significant\n>> updates.\n>>\n>> tl;dr: The way you manipulate the commit parents seems incorrect to me,\n>> but perhaps there is enough prior art in the way we simplify parents to\n>> make that acceptable. Someone else will need to chime in on that part.\n> \n> First, thank you for taking the time look at this.  I understand your\n> hesitation about the \"amputation\" of the history, but in some sense\n> that's the point of this option.  I really want to be ignorant of the\n> details of when the fork branched off.  I would like the reported\n> history to be appear nearly equivalent to a rebase-and-fastforward only\n> merge style, which results in a much simpler git log --graph.\n> \n>> It may be possible to do this \"drop edges\" entirely inside of graph.c\n>> (the graph rendering code) instead of revision.c, which would automatically\n>> work with the performance gains from the newer topo-walk algorithm.\n> \n> Non-local information about the commit graph needs to be used to do this\n> amputation of the history.  We cannot know how many parents we want to\n> display until we've completely explored all the parents of that node.\n> Unfortunately, that means that the whole graph needs to be loaded, and I\n> cannot really see how there would be any gain by doing this in graph.c.\n> \n> Caveat: there are semi-streaming DFS implementations (i.e., O(n log n)\n> space) that we might be able to use to get the first line out the door\n> quicker. I would, however, like to leave that to another patch.\n> \n> I will also add that, for the tests I've done, all performance penalties\n> have been insignificant (less than ~5% for showing the first commit),\n> while there are significant performance _improvements_, e.g., ~40% for\n> displaying the full tree.\n> \n> A notable exception is --all, which can be ~50x faster for the full\n> output, but is often dramatically slower to show anything (i.e., the\n> first line).\n> \n>> There are enough deviations from code and test style that this will\n>> need a significant revision regardless.\n> \n> (Please see forthcoming revision 3).\n> \n>>> This second revision of the patch sets revs->limited.  This forces the\n>>> graph of commits to be loaded, and simplfiy_forks() therefore reliably\n>>> traverses it.  This addresses the test failures mentioned before (see [1]).\n>>\n>> This will have a significant performance impact on the option, as you will\n>> not see even the first result until the DFS has completed.\n> \n> First of all, short of using some other, more sophisticated streaming\n> version of this algorithm, the full DFS must finish before the first\n> commit having two (or more) parents can be shown.\n> \n> That said, the performance is not significantly affected:\n> \n> I ran the following test (2.26.2, with my patch on top of it):\n> (git lg = git log --graph --pretty=oneline)\n> \n>  % time git lg -n1 --ignore-merge-bases e896a286df > /dev/null\n>  0.73s user 0.02s system 99% cpu 0.746 total\n> \n>  % time git lg -n1 e896a286df > /dev/null\n>  0.72s user 0.01s system 99% cpu 0.731 total\n> \n>  For the linux git repo:\n> \n>  % time git lg -n1 --ignore-merge-bases v5.7-rc3 >/dev/null\n>  9.25s user 0.39s system 99% cpu 9.646 total\n> \n>  % time git lg -n1 v5.7-rc3 >/dev/null\n>  9.02s user 0.35s system 99% cpu 9.378 total\n> \n> So the performance seems basically unaffected for very limited graphs.\n> It's also about 40% faster for complicated ones (as mentioned in my\n> first email):\n> \n>  % time git lg --ignore-merge-bases e870325ee8 > /dev/null\n>  0.83s user 0.06s system 99% cpu 0.886 total\n> \n>  % time git lg e870325ee8 > /dev/null\n>  1.41s user 0.03s system 99% cpu 1.443 total\n> \n>  For the linux git repo:\n> \n>  % time git lg --ignore-merge-bases v5.7-rc3 >/dev/null\n>  11.86s user 0.62s system 99% cpu 12.489 total\n> \n>  % time git lg v5.7-rc3 >/dev/null\n>  21.56s user 0.55s system 99% cpu 22.108 total\n\nFirst, run `git commit-graph write --reachable` to create a commit-graph\nfile which has generation numbers. In this case, I get the following:\n\n$ time git log --oneline --graph v5.7-rc3 >/dev/null\n\nreal    0m13.548s\nuser    0m13.348s\nsys     0m0.200s\n\n$ time git log --oneline --graph -n 1 v5.7-rc3 >/dev/null\n\nreal    0m0.007s\nuser    0m0.004s\nsys     0m0.004s\n\nNotice exactly how much better this gets for the first result with that\nfile.\n\n> This is because the amputated graph is much simpler, and the rest of the\n> code needs to do much less work.\n> \n> Passing --all is another beast, and does indeed suffer:\n> \n>  % time git lg --ignore-merge-bases --all >/dev/null\n>  4.06s user 0.04s system 99% cpu 4.105 total\n> \n>  % time git lg --all >/dev/null\n>  189.59s user 0.04s system 99% cpu 3:09.65 total\n> \n>  (and for the first line)\n> \n>  % time git lg -n1 --ignore-merge-bases --all >/dev/null\n>  3.86s user 0.02s system 99% cpu 3.874 total\n> \n>  % time git lg -n1 --all >/dev/null\n>  0.83s user 0.02s system 99% cpu 0.848 total\n> \n> (If you need to use --all for the Linux git repo, you should not use\n> --ignore-merge-bases).\n\nI think this is a deficiency in your implementation, not a hard rule\nabout how these options would need to interact.\n\nThanks,\n-Stolee\n\n"},{"id":"396773","messageId":"xmqq4kszoa2w.fsf@gitster.c.googlers.com","threadId":"53330","inReplyTo":"3a2605b6-c612-f70c-a11e-1e1cc3f59184@gmail.com","subject":"Re: [PATCH 1/3 v3] Clean up t6016-rev-list-graph-simplify-history","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-05-01T17:10:15Z","receivedAt":"2020-05-01T17:10:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Antonio Russo <antonio.e.russo@gmail.com> writes:\n\n> +check_graph () {\n> +\tcat >expected &&\n\nNot a new issue, but we may want to fix this to align to majority of\ntests by calling it \"expect\".\n\n> +\tgit rev-list --graph \"$@\" | sed \"$(cat sedscript)\" > actual &&\n\nStyle. No SP between > (or < for that matter) and the filename.\n\nThe \"sed\" utility can be told to read its script from a file with\nits \"-f\" option.\n\nCorrectness.  Never run \"git\" command that is the target being\ntested on the left side of a pipe.  It will hide the exit status.\n\n> +\ttest_cmp expected actual\n> +}\n\n>  test_expect_success 'set up rev-list --graph test' '\n>  \t# 3 commits on branch A\n>  \ttest_commit A1 foo.txt &&\n> @@ -43,76 +49,62 @@ test_expect_success 'set up rev-list --graph test' '\n>\n>  \ttest_commit A7 bar.txt &&\n>\n> -\t# Store commit names in variables for later use\n> -\tA1=$(git rev-parse --verify A1) &&\n> -\tA2=$(git rev-parse --verify A2) &&\n> -\tA3=$(git rev-parse --verify A3) &&\n> -\tA4=$(git rev-parse --verify A4) &&\n> -\tA5=$(git rev-parse --verify A5) &&\n> -\tA6=$(git rev-parse --verify A6) &&\n> -\tA7=$(git rev-parse --verify A7) &&\n> -\tB1=$(git rev-parse --verify B1) &&\n> -\tB2=$(git rev-parse --verify B2) &&\n> -\tC1=$(git rev-parse --verify C1) &&\n> -\tC2=$(git rev-parse --verify C2) &&\n> -\tC3=$(git rev-parse --verify C3) &&\n> -\tC4=$(git rev-parse --verify C4)\n> -\t'\n> +\techo \"s/ *$//;\" > sedscript &&\n> +\t( for tag in $(git tag -l) ; do echo \"s/$(git rev-parse --verify $tag)/$tag/;\" >> sedscript ; done )\n\nAvoid unreadable one-liner with needless subshell.\n\nI suspect that this is a task for-each-ref was designed for,\nsomething along the lines of...\n\n\tgit for-each-ref --format='s|%(objectname)|%(refname:short)|' \\\n\t\trefs/tags/ >>sedScript\n\n> +'\n>\n>  test_expect_success '--graph --all' '\n> -\trm -f expected &&\n> -\techo \"* $A7\" >> expected &&\n> -\techo \"*   $A6\" >> expected &&\n> -\techo \"|\\\\  \" >> expected &&\n> -\techo \"| * $C4\" >> expected &&\n> -\techo \"| * $C3\" >> expected &&\n> -\techo \"* | $A5\" >> expected &&\n> -\techo \"| |   \" >> expected &&\n> -\techo \"|  \\\\  \" >> expected &&\n> -\techo \"*-. | $A4\" >> expected &&\n> -\techo \"|\\\\ \\\\| \" >> expected &&\n> -\techo \"| | * $C2\" >> expected &&\n> -\techo \"| | * $C1\" >> expected &&\n> -\techo \"| * | $B2\" >> expected &&\n> -\techo \"| * | $B1\" >> expected &&\n> -\techo \"* | | $A3\" >> expected &&\n> -\techo \"| |/  \" >> expected &&\n> -\techo \"|/|   \" >> expected &&\n> -\techo \"* | $A2\" >> expected &&\n> -\techo \"|/  \" >> expected &&\n> -\techo \"* $A1\" >> expected &&\n> -\tgit rev-list --graph --all > actual &&\n> -\ttest_cmp expected actual\n> -\t'\n> +\tcheck_graph --all <<-\\EOF\n> +\t* A7\n> +\t*   A6\n> +\t|\\\n> +\t| * C4\n> +\t| * C3\n> +\t* | A5\n> +\t| |\n> +\t|  \\\n> +\t*-. | A4\n> +\t|\\ \\|\n> +\t| | * C2\n> +\t| | * C1\n> +\t| * | B2\n> +\t| * | B1\n> +\t* | | A3\n> +\t| |/\n> +\t|/|\n> +\t* | A2\n> +\t|/\n> +\t* A1\n> +\tEOF\n\nMuch nicer to see.\n\nHaving said all that, I am not sure if this change of design is\nsound.\n\nThe original approach would have worked even if two or more of these\ntags pointed at the same object.  Your version will pick one of\nthem.  If two tags, say A5 and C8, pointed at the same commit, and\nthe illustration given to check_graph helper from its standard\noutput labeled a commit as C8, wouldn't the actual output converted\nto show A5 with your sedScript approach?\n\nI think it is salvageable by changing the direction you munge.\nInstead of munging the rev-list output, you can store it as-is in\n\"actual\", and instead pass the illustration that comes from the\nstandard input of the check_graph helper through sed to expand the\nsymbolic names to actual object names before comparing. i.e.\n\n\tcheck_graph () {\n\t\tsed -f expand_tag_to_objects.sed >expect &&\n\t\tgit rev-list --graph \"$@\" >actual &&\n\t\ttest_cmp expect actual\n\t}\n\nNote that I renamed the overly generic \"sedscript\" to a name that\nreflects the purpose of the file (and the contents being of a\ncertain type is conveyed by .sed suffix, just like you'd use\nsuffixes like .c, .txt).  A good discipline to learn, I would say.\n\nThanks.\n"},{"id":"396823","messageId":"37b157a3-f2d6-f459-2f2c-2ab53ba2f7ac@kdbg.org","threadId":"53330","inReplyTo":"1716d20d-6f0d-3872-cf36-6fc8d7bdb457@gmail.com","subject":"Re: [PATCH 2/3 v3] Teach git-rev-list --ignore-merge-bases","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2020-05-02T13:25:31Z","receivedAt":"2020-05-02T13:25:37Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 01.05.20 um 16:22 schrieb Antonio Russo:\n> +--ignore-merge-bases::\n> +\tShow commits that are introduced by each merge before showing\n> +\tthe first parent of the merge but remove edges from those commits\n> +\tto commits reachable from the first parent. When used with\n> +\t`--graph`, this can help visualize repositories with many merges\n> +\twhen you are not interested in the merge base used for each\n> +\tmerge. It also reduces the width of the graph visualization\n> +\twhen used with `--graph`.\n\nI wonder whether there is some potential to prettify another aspect of\n--graph once this feature is in place: In particular, when I *am*\ninterested in merge-bases, I use --boundary, and I get this chart:\n\n$ git log --graph --boundary --oneline --no-decorate 7d28d69174~4..7d28d69174\n\n*   7d28d69174 Merge branch 'jc/allow-strlen-substitution-in-shell-scripts'\n|\\  \n| * 78725ebda9 CodingGuidelines: allow ${#posix} == strlen($posix)\n* |   dfdce31ce6 Merge branch 'en/pull-do-not-rebase-after-fast-forwarding'\n|\\ \\  \n| * | fbae70ddc6 pull: avoid running both merge and rebase\n| |/  \n* |   b660a76d0f Merge branch 'dl/wrapper-fix-indentation'\n|\\ \\  \n| * | 7cd54d37dc wrapper: indent with tabs\n* | |   3d6c56dd66 Merge branch 'ag/sequencer-i18n-messages'\n|\\ \\ \\  \n| * | | 4d55d63bde sequencer: mark messages for translation\n| o | | 3bab5d5625 The second batch post 2.26 cycle\n|  / /  \no / / 9f471e4b95 Merge branch 'rs/pull-options-sync-code-and-doc'\n / /  \no / 0b6806b9e4 xread, xwrite: limit size of IO to 8MB\n /  \no b6d4d82bd5 msvc: accommodate for vcpkg's upgrade to OpenSSL v1.1.x\n\nbut I would prefer to see something like this:\n\n*   7d28d69174 Merge branch 'jc/allow-strlen-substitution-in-shell-scripts'\n|\\  \n| * 78725ebda9 CodingGuidelines: allow ${#posix} == strlen($posix)\n* |   dfdce31ce6 Merge branch 'en/pull-do-not-rebase-after-fast-forwarding'\n|\\ \\  \n| * | fbae70ddc6 pull: avoid running both merge and rebase\n| |/\n| o b6d4d82bd5 msvc: accommodate for vcpkg's upgrade to OpenSSL v1.1.x  \n*   b660a76d0f Merge branch 'dl/wrapper-fix-indentation'\n|\\  \n| * 7cd54d37dc wrapper: indent with tabs\n| o 0b6806b9e4 xread, xwrite: limit size of IO to 8MB\n*   3d6c56dd66 Merge branch 'ag/sequencer-i18n-messages'\n|\\  \n| * 4d55d63bde sequencer: mark messages for translation\n| o 3bab5d5625 The second batch post 2.26 cycle\no 9f471e4b95 Merge branch 'rs/pull-options-sync-code-and-doc'\n\nMaybe that is just an easy fall-out?\n\n> diff --git a/object.h b/object.h\n> index b22328b838..0bf6fb0d55 100644\n> --- a/object.h\n> +++ b/object.h\n> @@ -59,7 +59,7 @@ struct object_array {\n> \n>  /*\n>   * object flag allocation:\n> - * revision.h:               0---------10         15                   25----28\n> + * revision.h:               0---------10         15                   23----28\n\nI think the intent is that the line is like a ruler with marks: you\nshould move \"23\" sufficiently far to the left, because the \"23\" mark\ncannot be at the same spot where the \"25\" mark was.\n\n(I'm not reviewing this patch as I am illiterate when it comes to the\nrevision walker, I just happened to notice this when I skimmed the\npatch.)\n\n>   * fetch-pack.c:             01\n>   * negotiator/default.c:       2--5\n>   * walker.c:                 0-2\n\n-- Hannes\n"},{"id":"396825","messageId":"e14bbff1-e77a-f346-aa33-5d4ea1bccdb8@gmail.com","threadId":"53330","inReplyTo":"37b157a3-f2d6-f459-2f2c-2ab53ba2f7ac@kdbg.org","subject":"Re: [PATCH 2/3 v3] Teach git-rev-list --ignore-merge-bases","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-05-02T14:21:50Z","receivedAt":"2020-05-02T14:21:54Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"On 5/2/20 7:25 AM, Johannes Sixt wrote:\n> Am 01.05.20 um 16:22 schrieb Antonio Russo:\n>> +--ignore-merge-bases::\n>> +\tShow commits that are introduced by each merge before showing\n>> +\tthe first parent of the merge but remove edges from those commits\n>> +\tto commits reachable from the first parent. When used with\n>> +\t`--graph`, this can help visualize repositories with many merges\n>> +\twhen you are not interested in the merge base used for each\n>> +\tmerge. It also reduces the width of the graph visualization\n>> +\twhen used with `--graph`.\n> \n> I wonder whether there is some potential to prettify another aspect of\n> --graph once this feature is in place: In particular, when I *am*\n> interested in merge-bases, I use --boundary, and I get this chart:\n> \n> $ git log --graph --boundary --oneline --no-decorate 7d28d69174~4..7d28d69174\n> \n> *   7d28d69174 Merge branch 'jc/allow-strlen-substitution-in-shell-scripts'\n> |\\  \n> | * 78725ebda9 CodingGuidelines: allow ${#posix} == strlen($posix)\n> * |   dfdce31ce6 Merge branch 'en/pull-do-not-rebase-after-fast-forwarding'\n> |\\ \\  \n> | * | fbae70ddc6 pull: avoid running both merge and rebase\n> | |/  \n> * |   b660a76d0f Merge branch 'dl/wrapper-fix-indentation'\n> |\\ \\  \n> | * | 7cd54d37dc wrapper: indent with tabs\n> * | |   3d6c56dd66 Merge branch 'ag/sequencer-i18n-messages'\n> |\\ \\ \\  \n> | * | | 4d55d63bde sequencer: mark messages for translation\n> | o | | 3bab5d5625 The second batch post 2.26 cycle\n> |  / /  \n> o / / 9f471e4b95 Merge branch 'rs/pull-options-sync-code-and-doc'\n>  / /  \n> o / 0b6806b9e4 xread, xwrite: limit size of IO to 8MB\n>  /  \n> o b6d4d82bd5 msvc: accommodate for vcpkg's upgrade to OpenSSL v1.1.x\n> \n> but I would prefer to see something like this:\n> \n> *   7d28d69174 Merge branch 'jc/allow-strlen-substitution-in-shell-scripts'\n> |\\  \n> | * 78725ebda9 CodingGuidelines: allow ${#posix} == strlen($posix)\n> * |   dfdce31ce6 Merge branch 'en/pull-do-not-rebase-after-fast-forwarding'\n> |\\ \\  \n> | * | fbae70ddc6 pull: avoid running both merge and rebase\n> | |/\n> | o b6d4d82bd5 msvc: accommodate for vcpkg's upgrade to OpenSSL v1.1.x  \n> *   b660a76d0f Merge branch 'dl/wrapper-fix-indentation'\n> |\\  \n> | * 7cd54d37dc wrapper: indent with tabs\n> | o 0b6806b9e4 xread, xwrite: limit size of IO to 8MB\n> *   3d6c56dd66 Merge branch 'ag/sequencer-i18n-messages'\n> |\\  \n> | * 4d55d63bde sequencer: mark messages for translation\n> | o 3bab5d5625 The second batch post 2.26 cycle\n> o 9f471e4b95 Merge branch 'rs/pull-options-sync-code-and-doc'\n> \n> Maybe that is just an easy fall-out?\n\nYeah, I noticed this too.  What we want is to create a spanning tree by left-first\nDFS (amputating edges connecting to already visited vertices), and then walk the\namputated tree in a right-first DFS (and then not sort the commits any further).\n\nThe tricky part is getting the results of the right-first DFS before the left-first\n(amputation) DFS finishes.  I'm working on it.\n\n>> diff --git a/object.h b/object.h\n>> index b22328b838..0bf6fb0d55 100644\n>> --- a/object.h\n>> +++ b/object.h\n>> @@ -59,7 +59,7 @@ struct object_array {\n>>\n>>  /*\n>>   * object flag allocation:\n>> - * revision.h:               0---------10         15                   25----28\n>> + * revision.h:               0---------10         15                   23----28\n> \n> I think the intent is that the line is like a ruler with marks: you\n> should move \"23\" sufficiently far to the left, because the \"23\" mark\n> cannot be at the same spot where the \"25\" mark was.\n\nI though this was only a schematic ruler, but, counting it now, it is exact.\nI'll fix it.\n\n> (I'm not reviewing this patch as I am illiterate when it comes to the\n> revision walker, I just happened to notice this when I skimmed the\n> patch.)\n\nThank you,\nAntonio\n"},{"id":"396832","messageId":"01dc74f9-8bc6-cb8d-4eca-6495ffb04826@gmail.com","threadId":"53330","inReplyTo":"xmqq4kszoa2w.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3 v3] Clean up t6016-rev-list-graph-simplify-history","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-05-02T15:27:46Z","receivedAt":"2020-05-02T15:27:50Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"On 5/1/20 11:10 AM, Junio C Hamano wrote:\n> Antonio Russo <antonio.e.russo@gmail.com> writes:\n> \n>> +check_graph () {\n>> +\tcat >expected &&\n> \n> Not a new issue, but we may want to fix this to align to majority of\n> tests by calling it \"expect\".\n> \n>> +\tgit rev-list --graph \"$@\" | sed \"$(cat sedscript)\" > actual &&\n> \n> Style. No SP between > (or < for that matter) and the filename.\n> \n> The \"sed\" utility can be told to read its script from a file with\n> its \"-f\" option.\n> \n> Correctness.  Never run \"git\" command that is the target being\n> tested on the left side of a pipe.  It will hide the exit status.\n\n>> -\t'\n>> +\techo \"s/ *$//;\" > sedscript &&\n>> +\t( for tag in $(git tag -l) ; do echo \"s/$(git rev-parse --verify $tag)/$tag/;\" >> sedscript ; done )\n> \n> Avoid unreadable one-liner with needless subshell.\n> \n> I suspect that this is a task for-each-ref was designed for,\n> something along the lines of...\n> \n> \tgit for-each-ref --format='s|%(objectname)|%(refname:short)|' \\\n> \t\trefs/tags/ >>sedScript\n> \n\nThanks, I've fixed these.\n\n> \n> Much nicer to see.\n> \n> Having said all that, I am not sure if this change of design is\n> sound.\n> \n> The original approach would have worked even if two or more of these\n> tags pointed at the same object.  Your version will pick one of\n> them.  If two tags, say A5 and C8, pointed at the same commit, and\n> the illustration given to check_graph helper from its standard\n> output labeled a commit as C8, wouldn't the actual output converted\n> to show A5 with your sedScript approach?\n> \n> I think it is salvageable by changing the direction you munge.\n> Instead of munging the rev-list output, you can store it as-is in\n> \"actual\", and instead pass the illustration that comes from the\n> standard input of the check_graph helper through sed to expand the\n> symbolic names to actual object names before comparing. i.e.\n> \n> \tcheck_graph () {\n> \t\tsed -f expand_tag_to_objects.sed >expect &&\n> \t\tgit rev-list --graph \"$@\" >actual &&\n> \t\ttest_cmp expect actual\n> \t}\n> \n> Note that I renamed the overly generic \"sedscript\" to a name that\n> reflects the purpose of the file (and the contents being of a\n> certain type is conveyed by .sed suffix, just like you'd use\n> suffixes like .c, .txt).  A good discipline to learn, I would say.\n\nI also fixed these.  I originally chose the other direction\n(oid->refname) to make the output more human readable.\n\nIf you think that's a worthwhile goal, I can figure something out.\n\nThat said, the patchset as it stands scratches my immediate need,\nand addressing D. Stolee's comments (in particular, making it work\nwith revs->limited==0) unfortunately has to be a lower priority\nfor me.\n\nI am not abandoning the patchset, but may be more delayed\nresponding to review.\n\nThanks,\nAntonio\n"}]}