{"thread":{"id":"53631","subject":"[PATCH 0/3] Ignore merge bases graph simplification","startedAt":"2020-06-07T16:22:39Z","lastAt":"2020-06-07T17:42:52Z","messageCount":5,"participants":["Antonio Russo","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"399244","messageId":"456a1271-4f17-5503-5d13-d0c97115e2fd@gmail.com","threadId":"53631","inReplyTo":null,"subject":"[PATCH 0/3] Ignore merge bases graph simplification","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-06-07T16:22:34Z","receivedAt":"2020-06-07T16:22:39Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"This patch series is a second attempt at providing a way to simplify the\ngraphical representation of forked branches that are merged back in.\nCurrently, when many branches are forked off the same commit, a\n\"mountain\" of the tails of the merge that connect to the merge base\naccumulate, making visual inspection of the --graph output challenging:\n\n% git log --graph --oneline 20514004dd -n20\n\n> * 20514004dd Start the post 2.27 cycle\n> *   54041832d7 Merge branch 'en/fast-import-looser-date'\n> |\\\n> | * d42a2fb72f fast-import: add new --date-format=raw-permissive format\n> * |   a0ba2bbbdd Merge branch 'mt/zsh-completion-optim'\n> |\\ \\\n> | * | a44a0a9fc4 completion: use native ZSH array pattern matching\n> * | |   e34df9a6e5 Merge branch 'la/diff-relative-config'\n> |\\ \\ \\\n> | * | | c28ded83fc diff: add config option relative\n> * | | |   de82fb45db Merge branch 'rs/checkout-b-track-error'\n> |\\ \\ \\ \\\n> | * | | | bb2198fb91 checkout: improve error messages for -b with extra argument\n> | * | | | 16ab794b82 checkout: add tests for -b and --track\n> * | | | |   202a2b8e71 Merge branch 'lo/sparse-universal-zero-init'\n> |\\ \\ \\ \\ \\\n> | * | | | | 1c96642326 sparse: allow '{ 0 }' to be used without warnings\n> | | |_|_|/\n> | |/| | |\n> * | | | |   1ab0dfde2c Merge branch 'cb/t5608-cleanup'\n> |\\ \\ \\ \\ \\\n> | * | | | | d63ae31962 t5608: avoid say() and use \"skip_all\" instead for consistency\n> | |/ / / /\n> * | | | |   70a1e331b0 Merge branch 'jx/pkt-line-doc-count-fix'\n> |\\ \\ \\ \\ \\\n> | * | | | | 2c31a7aa44 doc: fix wrong 4-byte length of pkt-line message\n> | |/ / / /\n> * | | | |   51b4708811 Merge branch 'jn/experimental-opts-into-proto-v2'\n> |\\ \\ \\ \\ \\\n> | * | | | | 3697caf4b9 config: let feature.experimental imply protocol.version=2\n> * | | | | |   7a8fec908a Merge branch 'bk/p4-prepare-p4-only-fix'\n> |\\ \\ \\ \\ \\ \\\n> | * | | | | | 2dfdd705ff git-p4.py: fix --prepare-p4-only error with multiple commits\n\nThis patch adds a new \"--ignore-merge-bases' parameter that, roughly,\nhides all of the information about the merge base:\n\n% git log --graph --oneline 20514004dd --ignore-merge-bases -n20\n\n> * 20514004dd Start the post 2.27 cycle\n> *   54041832d7 Merge branch 'en/fast-import-looser-date'\n> |\\\n> | * d42a2fb72f fast-import: add new --date-format=raw-permissive format\n> *   a0ba2bbbdd Merge branch 'mt/zsh-completion-optim'\n> |\\\n> | * a44a0a9fc4 completion: use native ZSH array pattern matching\n> *   e34df9a6e5 Merge branch 'la/diff-relative-config'\n> |\\\n> | * c28ded83fc diff: add config option relative\n> *   de82fb45db Merge branch 'rs/checkout-b-track-error'\n> |\\\n> | * bb2198fb91 checkout: improve error messages for -b with extra argument\n> | * 16ab794b82 checkout: add tests for -b and --track\n> *   202a2b8e71 Merge branch 'lo/sparse-universal-zero-init'\n> |\\\n> | * 1c96642326 sparse: allow '{ 0 }' to be used without warnings\n> *   1ab0dfde2c Merge branch 'cb/t5608-cleanup'\n> |\\\n> | * d63ae31962 t5608: avoid say() and use \"skip_all\" instead for consistency\n> *   70a1e331b0 Merge branch 'jx/pkt-line-doc-count-fix'\n> |\\\n> | * 2c31a7aa44 doc: fix wrong 4-byte length of pkt-line message\n> *   51b4708811 Merge branch 'jn/experimental-opts-into-proto-v2'\n> |\\\n> | * 3697caf4b9 config: let feature.experimental imply protocol.version=2\n> *   7a8fec908a Merge branch 'bk/p4-prepare-p4-only-fix'\n> |\\\n> | * 2dfdd705ff git-p4.py: fix --prepare-p4-only error with multiple commits\n\nThe significant changes since the last round of discussion are:\n\n1. A streaming version of the algorithm has been implemented.  No longer\nis revs->limited, with all of its very serious drawbacks, required.\n\n2. The commit->parents commit_list is no longer modified (amputated).\nInstead, a \"principle child\" is identified during a (heavily modified)\nindegree walk.\n\n3. Per D. Stolee's suggestion, the output of child->parent edges are\nsuppressed during graph emission (in particular, in\ngraph_is_interesting).\n\n4. No commit flags are used. All per-commit ancillary data is stored\nin a commit slab.\n\nI discarded J. Sixt's suggestion to change the format of the --boundary\noutput.  While I like the proposed format, I think the change is\northogonal to this (already large) change.\n\nThere are several outstanding issues that I would appreciate help with:\n\n1. I have developed some terminology to think about the concepts used\nhere.  They are definitely not conventional, and probably should be\nchanged.  I would appreciate feedback:\n\n - A \"skeleton walk\" is the streaming version of a left-first\n   DFS-generated spanning tree.  This is achieved using a carefully\n   generation-limited traversal of the commit graph.  *Edges* are\n   stored in a skel_walk_list structure.  This traversal should be\n   linear in the number of edges (but I'll admit I haven't actually\n   done this proof).\n\n - The \"guide commits\" are all of the commits in revs->commits.\n\n - A \"component\" (and this is particularly bad terminology) is the\n   collection of commits reachable from a guide commit, but not from\n   an earlier (\"higher priority\") guide commit.\n\n   This approach avoids any ambiguity in the output of\n   --ignore-merge-bases as to what commits are included at the merge\n   point, by always drawing any edge between components.  Notice that\n   the definition of a component means that no edges go from higher-\n   priority to lower-priority components (instead, those commits are\n   absorbed into the higher-priority component).\n\n - The \"principle child\" of a commit c is the first child in the\n   leftmost-first DFS that references c.  It is always in the same\n   component as c, and it is the only commit in that component whose\n   edge is drawn connecting to c.\n\nPresumably, all of these terms should be documented (with visuals)\nsomewhere.  If there is serious interest in this patch, I'm happy to do\nthis, but I'm loathe to waste time doing this until I start hearing some\nsort of positive feedback on what has become a significant time sink.\n\n2. The meat of the changes are monolithically collected into patch 2/3.\nIt does not make sense in my mind to implement functions that are not\nused anywhere, and then make first use them in another commit.  But, I\ncan split this up into the skeleton walk implementation and the graph\ndisplay, if wanted.\n\n3. A skel_walk_info structure is allocated at parameter parse time, and\ncurrently is never freed.  While this is certainly a memory leak, it is\nnot clear to me if there is a benefit to performing the cleanup, besides\ngetting clean valgrind output (and masking more serious memory leaks). I\nI didn't try to read everything in Documentation, but, besides an\nabundance of commits fixing memory leaks, I could not find a specific\npolicy regarding freeing memory before program termination.\n\n4. The implementation for revs->limited and !revs->limited is\nfrustratingly similar, but I cannot see any particular elegant way to\ndeduplicate the code.  The existing code also seems to suffer similarly.\n\nIs there movement forward on eliminating the whole rev->limited\ncode-path?  This is obviously out of scope for this patch set, but\nmaintaining two code-paths was a hassle for this one action, and I can\nimagine that it is much worse when multiplied by all of git's features.\n\n5. Similarly, the skel_walk is very similar to the existing indegree\nwalk.  But again, avoiding duplicated code leads to uncomfortable\n\n> if (skel) {\n>         ...\n> }\n\nblocks.  It also confuses gcc, which has trouble realizing that\nvariables were initialized in previous `if (skel)` blocks.  I'm then\nforced to resort to underhanded tricks: blanket initializing of\nvariables that should have been optimized out if !skel.\n\nDuplicating the entire function leads to cleaner and negligibly faster\ncode.  Frustratingly, but unsurprisingly, the meticulous careful\nskeleton walk that I've implemented is slightly slower than the\nexisting indegree walk, so it's a bad candidate to replace the old code.\n\nAny thoughts?\n\nThe entire patch set is also available at [1], which includes a few\ndebugging assertions enabled, and the excision of the unused\nfree_skel_info method (see 3, above) which otherwise breaks\n-Wunused-function.  It passes the full battery of tests there (as well\nas locally for me).\n\nBest,\nAntonio Russo\n\n[1] <https://github.com/aerusso/git/tree/mrs/imb-skel>\n"},{"id":"399245","messageId":"b215afe1-b6f2-03ca-4d25-f3e369a4f7e3@gmail.com","threadId":"53631","inReplyTo":"456a1271-4f17-5503-5d13-d0c97115e2fd@gmail.com","subject":"[PATCH 1/3] Clean up t6016-rev-list-graph-simplify-history","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-06-07T16:23:41Z","receivedAt":"2020-06-07T16:23:44Z","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 sed expansion of the expected output,\ninstead of shell substitutions and manually escaped echo's.\n\nReviewed-by: Junio C Hamano <gitster@pobox.com>\nSigned-off-by: Antonio Russo <antonio.e.russo@gmail.com>\n---\n t/t6016-rev-list-graph-simplify-history.sh | 350 ++++++++++-----------\n 1 file changed, 167 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..b6b2ab33ab 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,13 @@ test_description='--graph and simplified history'\n\n . ./test-lib.sh\n\n+check_graph () {\n+\tsed -f expand_tag_to_oid.sed >expect &&\n+\tgit rev-list --graph \"$@\" >actual &&\n+\tsed 's/ *$//' actual >actual.sanitized &&\n+\ttest_cmp expect actual.sanitized\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 +50,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+\tgit for-each-ref --format=\"s/%(refname:short)/%(objectname)/\" \\\n+\t\trefs/tags >expand_tag_to_oid.sed\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 +115,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.27.0\n\n"},{"id":"399246","messageId":"a2cb2897-6632-1e99-3dbe-4d8c7d2f9b39@gmail.com","threadId":"53631","inReplyTo":"456a1271-4f17-5503-5d13-d0c97115e2fd@gmail.com","subject":"[PATCH 2/3] Teach git-rev-list --ignore-merge-bases","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-06-07T16:24:43Z","receivedAt":"2020-06-07T16:24:50Z","isPatch":true,"sender":{"key":"antonio.e.russo@gmail.com","avatar":null},"body":"This new option simplifies the graph of commits for merges.  Edges to\ncommits reachable from more leftward parents, or more leftward parents\nof recursive child commits, are removed.  This \"skeleton\" spanning tree\neffectively omits all information about merge bases.\n\nWhen multiple tip commits are specified, all commits reachable from each\ntip commit (but not earlier tips) are simplified as above to form a\n\"component\".  All edges between components are displayed.\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\nSigned-off-by: Antonio Russo <antonio.e.russo@gmail.com>\n---\n Documentation/rev-list-options.txt |  13 ++\n builtin/log.c                      |   2 +-\n builtin/show-branch.c              |   2 +-\n commit.c                           | 132 +++++++++++++---\n commit.h                           |   4 +-\n graph.c                            |  40 +++--\n revision.c                         | 240 +++++++++++++++++++++++++++--\n revision.h                         |  17 ++\n 8 files changed, 404 insertions(+), 46 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex b01b2b6773..3470e710c8 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -363,6 +363,19 @@ 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+\tSimplify merges by removing edges to commits reachable from\n+\tmore leftware parents, or more leftward parents of recursive\n+\tchildren. When used with `--graph`, this can help visualize\n+\trepositories with many merges when you are not interested in\n+\tthe merge base used for each merge. It also reduces the width\n+\tof the graph visualization when used with `--graph`.\n+\n+\tWhen multiple tip commits are specified, all commits reachable\n+\tfrom each tip commit (but not earlier tips) are simplified as\n+\tabove to form a \"component\".  All edges between components are\n+\tdisplayed.\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/builtin/log.c b/builtin/log.c\nindex d104d5c688..2883fa2872 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -306,7 +306,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)\n \tint show_header = 1;\n\n \trevs->diffopt.close_file = 0;\n-\tsort_in_topological_order(&list, revs->sort_order);\n+\tsort_in_topological_order(&list, NULL, revs->sort_order);\n \twhile (list && i) {\n \t\tstruct commit *commit = list->item;\n \t\tswitch (simplify_commit(revs, commit)) {\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex 7e52ee9126..c766d61126 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -903,7 +903,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)\n \t\texit(0);\n\n \t/* Sort topologically */\n-\tsort_in_topological_order(&seen, sort_order);\n+\tsort_in_topological_order(&seen, NULL, sort_order);\n\n \t/* Give names to commits */\n \tif (!sha1_name && !no_name)\ndiff --git a/commit.c b/commit.c\nindex 87686a7055..aa5ff43c78 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -758,14 +758,18 @@ int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n /*\n  * Performs an in-place topological sort on the list supplied.\n  */\n-void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order)\n+void sort_in_topological_order(struct commit_list **list,\n+\t\t\t       struct skel_info *skel,\n+\t\t\t       enum rev_sort_order sort_order)\n {\n \tstruct commit_list *next, *orig = *list;\n \tstruct commit_list **pptr;\n \tstruct indegree_slab indegree;\n-\tstruct prio_queue queue;\n-\tstruct commit *commit;\n+\tstruct prio_queue queue, revqueue;\n+\tstruct commit *commit, *parent;\n \tstruct author_date_slab author_date;\n+\tint *comp_p = NULL, *comp_c = NULL, next_comp = 1;\n+\tstruct skel_datum *d_p = NULL, *d_c = NULL;\n\n \tif (!orig)\n \t\treturn;\n@@ -773,20 +777,10 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n\n \tinit_indegree_slab(&indegree);\n \tmemset(&queue, '\\0', sizeof(queue));\n+\tmemset(&revqueue, '\\0', sizeof(revqueue));\n\n-\tswitch (sort_order) {\n-\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n-\t\tqueue.compare = NULL;\n-\t\tbreak;\n-\tcase REV_SORT_BY_COMMIT_DATE:\n-\t\tqueue.compare = compare_commits_by_commit_date;\n-\t\tbreak;\n-\tcase REV_SORT_BY_AUTHOR_DATE:\n+\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n \t\tinit_author_date_slab(&author_date);\n-\t\tqueue.compare = compare_commits_by_author_date;\n-\t\tqueue.cb_data = &author_date;\n-\t\tbreak;\n-\t}\n\n \t/* Mark them and clear the indegree */\n \tfor (next = orig; next; next = next->next) {\n@@ -795,19 +789,100 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \t\t/* also record the author dates, if needed */\n \t\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n \t\t\trecord_author_date(&author_date, commit);\n+\t\tprio_queue_put(&queue, commit);\n \t}\n\n+\t/*\n+\t * When performing a skeleton walk, all commits must be processed from\n+\t * highest priority to lowest priority.  The highest priority commits\n+\t * appear first in orig, so we must reverse the queue to ensure they\n+\t * are processed first.\n+\t */\n+\tif (skel)\n+\t\tprio_queue_reverse(&queue);\n+\n \t/* update the indegree */\n-\tfor (next = orig; next; next = next->next) {\n-\t\tstruct commit_list *parents = next->item->parents;\n-\t\twhile (parents) {\n+\twhile ((commit = prio_queue_get(&queue)) != NULL) {\n+\t\tif (skel) {\n+\t\t\tcomp_c = &skel_slab_at(&skel->slab, commit)->component;\n+\n+\t\t\t/*\n+\t\t\t * Store if we have visited the commit in its sign bit.\n+\t\t\t *\n+\t\t\t * Skip if we already visited, or mark that this commit\n+\t\t\t * has been visisted.\n+\t\t\t *\n+\t\t\t * Assign a new component if none has already been\n+\t\t\t * propagated to the commit.\n+\t\t\t */\n+\t\t\tif (*comp_c > 0)\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (!*comp_c)\n+\t\t\t\t*comp_c = next_comp++;\n+\t\t\telse\n+\t\t\t\t*comp_c = -*comp_c;\n+\t\t}\n+\n+\t\tfor (struct commit_list *parents = commit->parents;\n+\t\t     parents; parents = parents->next) {\n \t\t\tstruct commit *parent = parents->item;\n \t\t\tint *pi = indegree_slab_at(&indegree, parent);\n\n-\t\t\tif (*pi)\n+\t\t\tif (!*pi)\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (skel) {\n+\t\t\t\td_p = skel_slab_at(&skel->slab, parent);\n+\t\t\t\t/*\n+\t\t\t\t * Back-propagate the child's component, and\n+\t\t\t\t * mark the principle child.\n+\t\t\t\t *\n+\t\t\t\t * Only count the first intra-component\n+\t\t\t\t * reference. but count all inter-component\n+\t\t\t\t * references.\n+\t\t\t\t *\n+\t\t\t\t * Override lower-priorty (higher numerical\n+\t\t\t\t * value) components.\n+\t\t\t\t */\n+\t\t\t\tcomp_p = &d_p->component;\n+\t\t\t\tif (!*comp_p || *comp_p > *comp_c) {\n+\t\t\t\t\t*comp_p = -*comp_c;\n+\t\t\t\t\td_p->child = commit;\n+\t\t\t\t\tprio_queue_put(&revqueue, parent);\n+\t\t\t\t\t(*pi)++;\n+\t\t\t\t} else if (*comp_p < *comp_c)\n+\t\t\t\t\t(*pi)++;\n+\t\t\t} else\n \t\t\t\t(*pi)++;\n-\t\t\tparents = parents->next;\n \t\t}\n+\n+\t\t/*\n+\t\t * More leftward commits are higher priority, and therefore\n+\t\t * must be processed first.\n+\t\t */\n+\t\tif (skel)\n+\t\t\twhile ((parent = prio_queue_get(&revqueue)) != NULL)\n+\t\t\t\tprio_queue_put(&queue, parent);\n+\t}\n+\n+\tif (skel) {\n+\t\tclear_prio_queue(&revqueue);\n+\t\tclear_prio_queue(&queue);\n+\t}\n+\n+\t/* reuse the priority queue */\n+\tswitch (sort_order) {\n+\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n+\t\tqueue.compare = NULL;\n+\t\tbreak;\n+\tcase REV_SORT_BY_COMMIT_DATE:\n+\t\tqueue.compare = compare_commits_by_commit_date;\n+\t\tbreak;\n+\tcase REV_SORT_BY_AUTHOR_DATE:\n+\t\tqueue.compare = compare_commits_by_author_date;\n+\t\tqueue.cb_data = &author_date;\n+\t\tbreak;\n \t}\n\n \t/*\n@@ -838,10 +913,18 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \t*list = NULL;\n \twhile ((commit = prio_queue_get(&queue)) != NULL) {\n \t\tstruct commit_list *parents;\n+\t\tif (skel) {\n+\t\t\td_c = skel_slab_at(&skel->slab, commit);\n+\t\t\tcomp_c = &d_c->component;\n+\t\t}\n\n \t\tfor (parents = commit->parents; parents ; parents = parents->next) {\n \t\t\tstruct commit *parent = parents->item;\n \t\t\tint *pi = indegree_slab_at(&indegree, parent);\n+\t\t\tif (skel) {\n+\t\t\t\td_p = skel_slab_at(&skel->slab, parent);\n+\t\t\t\tcomp_p = &d_p->component;\n+\t\t\t}\n\n \t\t\tif (!*pi)\n \t\t\t\tcontinue;\n@@ -850,9 +933,14 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \t\t\t * parents are only enqueued for emission\n \t\t\t * when all their children have been emitted thereby\n \t\t\t * guaranteeing topological order.\n+\t\t\t *\n+\t\t\t * If we are performing a skeleton walk, do not count\n+\t\t\t * intra-component references that are not from the\n+\t\t\t * principle child.\n \t\t\t */\n-\t\t\tif (--(*pi) == 1)\n-\t\t\t\tprio_queue_put(&queue, parent);\n+\t\t\tif (!skel || (*comp_p != *comp_c || d_p->child == commit))\n+\t\t\t\tif (--(*pi) == 1)\n+\t\t\t\t\tprio_queue_put(&queue, parent);\n \t\t}\n \t\t/*\n \t\t * all children of commit have already been\ndiff --git a/commit.h b/commit.h\nindex 1b2dea5d85..64d04d124f 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -183,6 +183,7 @@ struct commit_list *copy_commit_list(struct commit_list *list);\n void free_commit_list(struct commit_list *list);\n\n struct rev_info; /* in revision.h, it circularly uses enum cmit_fmt */\n+struct skel_info;\n\n int has_non_ascii(const char *text);\n const char *logmsg_reencode(const struct commit *commit,\n@@ -226,7 +227,8 @@ enum rev_sort_order {\n  *                            chain together.\n  *   REV_SORT_BY_COMMIT_DATE: show eligible commits in committer-date order.\n  */\n-void sort_in_topological_order(struct commit_list **, enum rev_sort_order);\n+void sort_in_topological_order(struct commit_list **, struct skel_info *,\n+\t\t\t       enum rev_sort_order);\n\n struct commit_graft {\n \tstruct object_id oid;\ndiff --git a/graph.c b/graph.c\nindex 4cd9915075..57fd51fb05 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -428,21 +428,43 @@ static void graph_ensure_capacity(struct git_graph *graph, int num_columns)\n  */\n static int graph_is_interesting(struct git_graph *graph, struct commit *commit)\n {\n-\t/*\n-\t * If revs->boundary is set, commits whose children have\n-\t * been shown are always interesting, even if they have the\n-\t * UNINTERESTING or TREESAME flags set.\n-\t */\n-\tif (graph->revs && graph->revs->boundary) {\n-\t\tif (commit->object.flags & CHILD_SHOWN)\n-\t\t\treturn 1;\n+\tstruct skel_datum *dat_p, *dat_c;\n+\tstruct rev_info *revs = graph->revs;\n+\tstruct skel_info *skel = NULL;\n+\n+\tif (revs->ignore_merge_bases)\n+\t\tskel = revs->skel_info;\n+\n+\tif (revs) {\n+\t\t/*\n+\t\t * If revs->boundary is set, commits whose children have\n+\t\t * been shown are always interesting, even if they have the\n+\t\t * UNINTERESTING or TREESAME flags set.\n+\t\t */\n+\t\tif (revs->boundary) {\n+\t\t\tif (commit->object.flags & CHILD_SHOWN)\n+\t\t\t\treturn 1;\n+\t\t}\n+\n+\t\t/*\n+\t\t * If revs->ignore_merge_bases is set, suppress intra-component\n+\t\t * edges that are not from the principle child.\n+\t\t */\n+\t\tif (skel) {\n+\t\t\tdat_p = skel_slab_at(&skel->slab, commit);\n+\t\t\tdat_c = skel_slab_at(&skel->slab, graph->commit);\n+\t\t\tif (dat_p->component == dat_c->component &&\n+\t\t\t    dat_p->child != graph->commit) {\n+\t\t\t\treturn 0;\n+\t\t\t}\n+\t\t}\n \t}\n\n \t/*\n \t * Otherwise, use get_commit_action() to see if this commit is\n \t * interesting\n \t */\n-\treturn get_commit_action(graph->revs, commit) == commit_show;\n+\treturn get_commit_action(revs, commit) == commit_show;\n }\n\n static struct commit_list *next_interesting_parent(struct git_graph *graph,\ndiff --git a/revision.c b/revision.c\nindex 60cca8c0b9..af676fd847 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -39,6 +39,22 @@ static const char *term_good;\n\n implement_shared_commit_slab(revision_sources, char *);\n\n+implement_shared_commit_slab(skel_slab, struct skel_datum);\n+\n+static struct skel_info *new_skel_info(void)\n+{\n+\tstruct skel_info *info = xcalloc(1, sizeof(struct skel_info));\n+\tmemset(info, '\\0', sizeof(struct skel_info));\n+\tinit_skel_slab(&info->slab);\n+\treturn info;\n+}\n+\n+static void free_skel_info(struct skel_info *info)\n+{\n+\tclear_skel_slab(&info->slab);\n+\tfree(info);\n+}\n+\n void show_object_with_name(FILE *out, struct object *obj, const char *name)\n {\n \tconst char *p;\n@@ -2204,6 +2220,10 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--topo-order\")) {\n \t\trevs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n \t\trevs->topo_order = 1;\n+\t} else if (!strcmp(arg, \"--ignore-merge-bases\")) {\n+\t\trevs->topo_order = 1;\n+\t\trevs->ignore_merge_bases = 1;\n+\t\trevs->skel_info = new_skel_info();\n \t} else if (!strcmp(arg, \"--simplify-merges\")) {\n \t\trevs->simplify_merges = 1;\n \t\trevs->topo_order = 1;\n@@ -3348,14 +3368,179 @@ static void indegree_walk_step(struct rev_info *revs)\n \t}\n }\n\n+/*\n+ * The skeleton walk is over edges in a graph.  Notationally, we refer to the\n+ * commit (item) and the child, because we will be interested in the parents of\n+ * item, not the children of child.\n+ */\n+struct skel_walk_list {\n+\tstruct commit *item;\n+\tstruct skel_walk_list *next;\n+\tstruct commit *child;\n+};\n+\n+static void swl_pop(struct skel_walk_list **stack)\n+{\n+\tstruct skel_walk_list *top = *stack;\n+\n+\tif (top) {\n+\t\t*stack = top->next;\n+\t\tfree(top);\n+\t}\n+\treturn;\n+}\n+\n+static struct skel_walk_list **swl_append(struct commit *item,\n+\t\t\t\t\t struct commit *child,\n+\t\t\t\t\t struct skel_walk_list **list_p)\n+{\n+\tstruct skel_walk_list *new_list = xmalloc(sizeof(struct skel_walk_list));\n+\n+\tif (parse_commit_gently(item, 1) < 0) {\n+\t\tprintf(\"WHAT!\\n\");\n+\t\treturn list_p; //XXX: !!?\n+\t}\n+\n+\tnew_list->item = item;\n+\tnew_list->next = *list_p;\n+\tnew_list->child = child;\n+\n+\t*list_p = new_list;\n+\treturn &new_list->next;\n+}\n+\n+static void skel_walk_step(struct rev_info *revs,\n+\t\t\t   struct skel_walk_list **next)\n+{\n+\tstruct indegree_slab *indegree = &revs->topo_walk_info->indegree;\n+\tstruct skel_info *skel = revs->skel_info;\n+\tstruct commit *commit = (*next)->item;\n+\tstruct skel_datum *d_i = skel_slab_at(&skel->slab, commit);\n+\tint comp_c, first = 1;\n+\n+\texplore_to_depth(revs, commit->generation);\n+\n+\t/*\n+\t * If the commit has already been visited, all the parents have already\n+\t * been processed, but we still must count inter-component references.\n+\t */\n+\tif (d_i->component) {\n+\t\tif ((*next)->child) {\n+\t\t\tcomp_c = skel_slab_at(&skel->slab, (*next)->child)->component;\n+\n+\t\t\tif (d_i->component < comp_c)\n+\t\t\t\t(*indegree_slab_at(indegree, commit))++;\n+\t\t}\n+\n+\t\tswl_pop(next);\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * We are visiting commit for the first time:\n+\t *  - count the indegree\n+\t *  - mark the principle child\n+\t *  - back-propagate the component\n+\t *\n+\t * If there is no principle child, allocate a new component.\n+\t */\n+\tif (!(*next)->child)\n+\t\td_i->component = skel->next_comp++;\n+\telse {\n+\t\td_i->child = (*next)->child;\n+\t\td_i->component = skel_slab_at(&skel->slab, d_i->child)->component;\n+\t\t*indegree_slab_at(indegree, commit) = 2;\n+\t}\n+\n+\t/*\n+\t * Push all parents onto the skeleton walk list, replacing *next.\n+\t */\n+\tfor (struct commit_list *parents = commit->parents;\n+\t     parents; parents = parents->next) {\n+\t\tstruct commit *parent = parents->item;\n+\n+\t\t/*\n+\t\t * Micro-optimization to reuse the skeleton walk list entry,\n+\t\t * if possible.\n+\t\t */\n+\t\tif (first) {\n+\t\t\t(*next)->item = parent;\n+\t\t\t(*next)->child = commit;\n+\n+\t\t\tnext = &(*next)->next;\n+\t\t\tfirst = 0;\n+\t\t} else\n+\t\t\tnext = swl_append(parent, commit, next);\n+\n+\t\tif (revs->first_parent_only)\n+\t\t\treturn;\n+\t}\n+\n+\tif (first)\n+\t\tswl_pop(next);\n+\n+\treturn;\n+}\n+\n static void compute_indegrees_to_depth(struct rev_info *revs,\n \t\t\t\t       uint32_t gen_cutoff)\n {\n \tstruct topo_walk_info *info = revs->topo_walk_info;\n \tstruct commit *c;\n-\twhile ((c = prio_queue_peek(&info->indegree_queue)) &&\n-\t       c->generation >= gen_cutoff)\n-\t\tindegree_walk_step(revs);\n+\tstruct skel_info *skel = NULL;\n+\tstruct skel_walk_list **next;\n+\tuint32_t t, p_gen_cutoff = gen_cutoff;\n+\n+\tif (revs->ignore_merge_bases)\n+\t\tskel = revs->skel_info;\n+\n+\tif (!skel) {\n+\t\twhile ((c = prio_queue_peek(&info->indegree_queue)) &&\n+\t\t       c->generation >= gen_cutoff)\n+\t\t\tindegree_walk_step(revs);\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * Explore all edges originating from commits of appropriate generation\n+\t */\n+\tnext = &skel->walk;\n+\twhile (*next) {\n+\t\tif ((*next)->item->generation < gen_cutoff) {\n+\t\t\t/*\n+\t\t\t * Ideally, we would explore this edge right now, but\n+\t\t\t * we cannot, because we have not yet necessarily\n+\t\t\t * explored more leftward commits to this depth.\n+\t\t\t *\n+\t\t\t * Notice that (*next)->child is not NULL, because we\n+\t\t\t * always perform an initial search with depth of the\n+\t\t\t * maximum of all tip commits.\n+\t\t\t */\n+\t\t\tif ((*next)->child->generation < gen_cutoff) {\n+\t\t\t\tt = (*next)->item->generation;\n+\t\t\t\tif (t < p_gen_cutoff)\n+\t\t\t\t\tp_gen_cutoff = t;\n+\t\t\t}\n+\n+\t\t\tnext = &(*next)->next;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tskel_walk_step(revs, next);\n+\t}\n+\n+\t/*\n+\t * Double back to get the parents of commits above gen_cutoff.\n+\t */\n+\tnext = &skel->walk;\n+\twhile (*next) {\n+\t\tif ((*next)->item->generation < p_gen_cutoff) {\n+\t\t\tnext = &(*next)->next;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tskel_walk_step(revs, next);\n+\t}\n }\n\n static void reset_topo_walk(struct rev_info *revs)\n@@ -3375,6 +3560,12 @@ static void init_topo_walk(struct rev_info *revs)\n {\n \tstruct topo_walk_info *info;\n \tstruct commit_list *list;\n+\tstruct skel_walk_list **tail = NULL;\n+\tstruct skel_info *skel = NULL;\n+\n+\tif (revs->ignore_merge_bases)\n+\t\tskel = revs->skel_info;\n+\n \tif (revs->topo_walk_info)\n \t\treset_topo_walk(revs);\n\n@@ -3387,6 +3578,13 @@ static void init_topo_walk(struct rev_info *revs)\n \tmemset(&info->indegree_queue, 0, sizeof(info->indegree_queue));\n \tmemset(&info->topo_queue, 0, sizeof(info->topo_queue));\n\n+\tif (skel) {\n+\t\ttail = &skel->walk;\n+\t\t*tail = NULL;\n+\t\tskel->next_comp = 1;\n+\t}\n+\n+\n \tswitch (revs->sort_order) {\n \tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n \t\tinfo->topo_queue.compare = NULL;\n@@ -3411,16 +3609,23 @@ static void init_topo_walk(struct rev_info *revs)\n \t\tif (parse_commit_gently(c, 1))\n \t\t\tcontinue;\n\n-\t\ttest_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);\n-\t\ttest_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);\n-\n \t\tif (c->generation < info->min_generation)\n \t\t\tinfo->min_generation = c->generation;\n\n-\t\t*(indegree_slab_at(&info->indegree, c)) = 1;\n+\t\ttest_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);\n\n \t\tif (revs->sort_order == REV_SORT_BY_AUTHOR_DATE)\n \t\t\trecord_author_date(&info->author_date, c);\n+\n+\t\t*(indegree_slab_at(&info->indegree, c)) = 1;\n+\n+\t\tif (skel) {\n+\t\t\ttail = swl_append(c, NULL, tail);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\ttest_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);\n+\n \t}\n \tcompute_indegrees_to_depth(revs, info->min_generation);\n\n@@ -3457,6 +3662,11 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_list *p;\n \tstruct topo_walk_info *info = revs->topo_walk_info;\n+\tstruct skel_info *skel = revs->skel_info;\n+\n+\tif (!revs->ignore_merge_bases)\n+\t\tskel = NULL;\n+\n \tif (process_parents(revs, commit, NULL, NULL) < 0) {\n \t\tif (!revs->ignore_missing_links)\n \t\t\tdie(\"Failed to traverse parents of commit %s\",\n@@ -3480,9 +3690,11 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n\n \t\tpi = indegree_slab_at(&info->indegree, parent);\n\n-\t\t(*pi)--;\n-\t\tif (*pi == 1)\n-\t\t\tprio_queue_put(&info->topo_queue, parent);\n+\t\tif (!skel ||\n+\t\t    (skel_slab_at(&skel->slab, parent)->component != skel_slab_at(&skel->slab, commit)->component ||\n+\t\t     skel_slab_at(&skel->slab, parent)->child == commit ))\n+\t\t\tif (--(*pi) == 1)\n+\t\t\t\tprio_queue_put(&info->topo_queue, parent);\n\n \t\tif (revs->first_parent_only)\n \t\t\treturn;\n@@ -3531,7 +3743,9 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\tif (limit_list(revs) < 0)\n \t\t\treturn -1;\n \t\tif (revs->topo_order)\n-\t\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n+\t\t\tsort_in_topological_order(&revs->commits,\n+\t\t\t\t\t\t  revs->skel_info,\n+\t\t\t\t\t\t  revs->sort_order);\n \t} else if (revs->topo_order)\n \t\tinit_topo_walk(revs);\n \tif (revs->line_level_traverse)\n@@ -3987,11 +4201,13 @@ static void create_boundary_commit_list(struct rev_info *revs)\n \t\tcommit_list_insert(c, &revs->commits);\n \t}\n\n+\trevs->ignore_merge_bases = 0;\n+\n \t/*\n \t * If revs->topo_order is set, sort the boundary commits\n \t * in topological order\n \t */\n-\tsort_in_topological_order(&revs->commits, revs->sort_order);\n+\tsort_in_topological_order(&revs->commits, NULL, revs->sort_order);\n }\n\n static struct commit *get_revision_internal(struct rev_info *revs)\ndiff --git a/revision.h b/revision.h\nindex 93491b79d4..b33fbe8829 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -88,6 +88,21 @@ struct rev_cmdline_info {\n struct oidset;\n struct topo_walk_info;\n\n+struct skel_datum {\n+\tint component;\n+\tstruct commit *child;\n+};\n+\n+define_shared_commit_slab(skel_slab, struct skel_datum);\n+\n+struct skel_walk_list;\n+\n+struct skel_info {\n+\tstruct skel_walk_list *walk;\n+\tint next_comp;\n+\tstruct skel_slab slab;\n+};\n+\n struct rev_info {\n \t/* Starting list */\n \tstruct commit_list *commits;\n@@ -137,6 +152,7 @@ struct rev_info {\n \t\t\tshow_pulls:1,\n \t\t\ttopo_order:1,\n \t\t\tsimplify_merges:1,\n+\t\t\tignore_merge_bases:1,\n \t\t\tsimplify_by_decoration:1,\n \t\t\tsingle_worktree:1,\n \t\t\ttag_objects:1,\n@@ -307,6 +323,7 @@ struct rev_info {\n \t * This is loaded from the commit-graph being used.\n \t */\n \tstruct bloom_filter_settings *bloom_filter_settings;\n+\tstruct skel_info *skel_info;\n };\n\n int ref_excluded(struct string_list *, const char *path);\n-- \n2.27.0\n\n"},{"id":"399247","messageId":"dba7f300-3418-de23-bbc2-e663c8c90efe@gmail.com","threadId":"53631","inReplyTo":"456a1271-4f17-5503-5d13-d0c97115e2fd@gmail.com","subject":"[PATCH 3/3] Add new tests of --ignore-merge-bases","fromName":"Antonio Russo","fromEmail":"antonio.e.russo@gmail.com","sentAt":"2020-06-07T16:26:13Z","receivedAt":"2020-06-07T16:26:16Z","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 t4217-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               | 169 +++++++++++++\n t/t4217-log-merges.sh                      | 273 +++++++++++++++++++++\n t/t6016-rev-list-graph-simplify-history.sh |  70 ++++++\n 3 files changed, 512 insertions(+)\n create mode 100755 t/t4217-log-merges.sh\n\ndiff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh\nindex 28d0779a8c..6baefef5e3 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,29 @@ 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| |/| |\n+\t| * | | 6_D\n+\t|  / /\n+\t* / / 6_C\n+\t|/ /\n+\t* / 6_B\n+\t|/\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 +504,39 @@ 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_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| * | | | 7_E\n+\t| | |/ /\n+\t| |/| |\n+\t| * | | 7_D\n+\t|  / /\n+\t* / / 7_C\n+\t|/ /\n+\t* / 7_B\n+\t|/\n+\t* 7_A\n+\tEOF\n+'\n+\n test_done\ndiff --git a/t/t4217-log-merges.sh b/t/t4217-log-merges.sh\nnew file mode 100755\nindex 0000000000..84b1973131\n--- /dev/null\n+++ b/t/t4217-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 b6b2ab33ab..2217e78fcd 100755\n--- a/t/t6016-rev-list-graph-simplify-history.sh\n+++ b/t/t6016-rev-list-graph-simplify-history.sh\n@@ -79,6 +79,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@@ -148,6 +169,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@@ -161,6 +195,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@@ -244,4 +290,28 @@ 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* | | | 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.27.0\n\n"},{"id":"399253","messageId":"xmqq1rmqn563.fsf@gitster.c.googlers.com","threadId":"53631","inReplyTo":"b215afe1-b6f2-03ca-4d25-f3e369a4f7e3@gmail.com","subject":"Re: [PATCH 1/3] Clean up t6016-rev-list-graph-simplify-history","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-07T17:42:44Z","receivedAt":"2020-06-07T17:42:52Z","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> Subject: Re: [PATCH 1/3] Clean up t6016-rev-list-graph-simplify-history\n\nHmph, didn't anybody give you guidance on the subjects the last\nround?\n\nIf this is a second round (I do not recall---I read too many\npatches), the subject should begin with\n\n\t[PATCH v2 1/3]\n\nand then \"<area>: one line summary\".  For test scripts, the script\nnumber is enough to identify the area the patch affects, e.g.\n\n\t[PATCH v2 1/3] t6016: simplify the way expected history is drawn\n\n> Simplifies the logic used to test rev-list, making adding new tests\n> easier.  Uses a heredoc and sed expansion of the expected output,\n> instead of shell substitutions and manually escaped echo's.\n\nJustify why this change is a good thing upfront, by (1) giving a\nshort summary of what is done in the current code and (2) saying\nwhat is suboptimal in it.\n\n    Many tests in this script prepare each line of the expected\n    --graph output separately with \"echo\", using bare object names\n    of commits shown in the graph (captured in shell variables), run\n    \"rev-list --graph\" with some other parameters and compares the\n    result.  The expected shape of the graph is hard to see and the\n    resulting code is repetitious.\n\nAnd then outline your solution, giving orders to the codebase to\n\"become like so\", in the next paragraph.\n\n    In order to add new tests easier, introduce a helper function\n    that takes extra parameters given to the \"rev-list --graph\" as\n    its arguments, and the expected output from its standard input\n    stream.  By allowing tagnames to be used in the expected output,\n    eliminate the need to capture commit object names in shell\n    variables.\n\ncf. Documentation/SubmittingPatches::imperative-mood\n\n> Reviewed-by: Junio C Hamano <gitster@pobox.com>\n\nI didn't review this version (in other words, I think you changed\nthe patch after I reviewed)---so do not write this line.  It is\nmisleading.\n\n>  . ./test-lib.sh\n>\n> +check_graph () {\n> +\tsed -f expand_tag_to_oid.sed >expect &&\n> +\tgit rev-list --graph \"$@\" >actual &&\n> +\tsed 's/ *$//' actual >actual.sanitized &&\n> +\ttest_cmp expect actual.sanitized\n> +}\n\nOK, so we prepare the mapping from tagname to objectname somewhere,\nfeed an expected output that uses tagname to this helper function\nand munge it into the file expect, and then compare it with the\nactual output.  \n\nWhy do we drop the trailing whitespace in the output before\ncomparing?  Is it because it does not matter?  Is it because it is\ncumbersome to spell in the expected output in the source?\n\nNot complaining.  But if we truly aim to make writing new tests\neasier, we should tell those who may write new tests what they are\nexpected to be doing when using this helper function in a comment\nbefore it to help them.  Some points I can think of off the top of\nmy head are:\n\n * The file expend_tag_to_oid.sed is created in a single \"setup\"\n   test;  when adding a new test, the shape of the history and new\n   tags used in it must be prepared before the \"for-each-ref\" that\n   produces the file in the \"setup\" test.\n\n * The arguments to the helper are given to \"git rev-list --graph\"\n   to be compared with the expected graph fed from the standard\n   input.\n\n * The expected graph can use tags and branches instead of object\n   names (and it is encouraged to do so) for readability.  You do\n   not mimick trailing whitespaces on the lines [*1*].\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\nI do agree that the resulting test is easier to understand.\n\nThanks.\n\n[Footnote *1*]\n\nThis is a tangent, but I wonder if somebody looked into how feasible\nit is to eliminate the trailing whitespace in the graph output.  It\nis OK to give whitespaces in anticipation of writing the commit\nobject names, but on a line in the output that exists only to show\nconnecting lines, where we know we will not write anything after the\ngraph, there is no excuse to end the graph part with a trailing\nwhitespace.\n\n"}]}