Ignore merge bases graph simplification
cover Ignore merge bases graph simplification
This patch series is a second attempt at providing a way to simplify the graphical representation of forked branches that are merged back in. Currently, when many branches are forked off the same commit, a "mountain" of the tails of the merge that connect to the merge base accumulate, making visual inspection of the --graph output challenging:
% git log --graph --oneline 20514004dd -n20
Quoted 25 lines
*
20514004ddStart the post 2.27 cycle
*54041832d7Merge branch 'en/fast-import-looser-date'
|\
| *d42a2fb72ffast-import: add new --date-format=raw-permissive format
* |a0ba2bbbddMerge branch 'mt/zsh-completion-optim'
|\ \| * | a44a0a9fc4 completion: use native ZSH array pattern matching * | | e34df9a6e5 Merge branch 'la/diff-relative-config' |\ \ \ | * | | c28ded83fc diff: add config option relative * | | | de82fb45db Merge branch 'rs/checkout-b-track-error' |\ \ \ \ | * | | | bb2198fb91 checkout: improve error messages for -b with extra argument | * | | | 16ab794b82 checkout: add tests for -b and --track * | | | | 202a2b8e71 Merge branch 'lo/sparse-universal-zero-init' |\ \ \ \ \ | * | | | | 1c96642326 sparse: allow '{ 0 }' to be used without warnings | | |_|_|/ | |/| | | * | | | | 1ab0dfde2c Merge branch 'cb/t5608-cleanup' |\ \ \ \ \ | * | | | | d63ae31962 t5608: avoid say() and use "skip_all" instead for consistency | |/ / / / * | | | | 70a1e331b0 Merge branch 'jx/pkt-line-doc-count-fix' |\ \ \ \ \
Quoted 8 lines
| * | | | | 2c31a7aa44 doc: fix wrong 4-byte length of pkt-line message | |/ / / / * | | | | 51b4708811 Merge branch 'jn/experimental-opts-into-proto-v2' |\ \ \ \ \ | * | | | | 3697caf4b9 config: let feature.experimental imply protocol.version=2 * | | | | | 7a8fec908a Merge branch 'bk/p4-prepare-p4-only-fix' |\ \ \ \ \ \ | * | | | | | 2dfdd705ff git-p4.py: fix --prepare-p4-only error with multiple commits
This patch adds a new "--ignore-merge-bases' parameter that, roughly, hides all of the information about the merge base:
% git log --graph --oneline 20514004dd --ignore-merge-bases -n20
Quoted 14 lines
*
20514004ddStart the post 2.27 cycle
*54041832d7Merge branch 'en/fast-import-looser-date'
|\
| *d42a2fb72ffast-import: add new --date-format=raw-permissive format
*a0ba2bbbddMerge branch 'mt/zsh-completion-optim'
|\
| *a44a0a9fc4completion: use native ZSH array pattern matching
*e34df9a6e5Merge branch 'la/diff-relative-config'
|\
| *c28ded83fcdiff: add config option relative
*de82fb45dbMerge branch 'rs/checkout-b-track-error'|\ | * bb2198fb91 checkout: improve error messages for -b with extra argument | * 16ab794b82 checkout: add tests for -b and --track
Quoted 15 lines
*
202a2b8e71Merge branch 'lo/sparse-universal-zero-init'
|\
| *1c96642326sparse: allow '{ 0 }' to be used without warnings
*1ab0dfde2cMerge branch 'cb/t5608-cleanup'
|\
| *d63ae31962t5608: avoidsay()and use "skip_all" instead for consistency
*70a1e331b0Merge branch 'jx/pkt-line-doc-count-fix'
|\
| *2c31a7aa44doc: fix wrong 4-byte length of pkt-line message
*51b4708811Merge branch 'jn/experimental-opts-into-proto-v2'
|\
| *3697caf4b9config: let feature.experimental imply protocol.version=2
*7a8fec908aMerge branch 'bk/p4-prepare-p4-only-fix'
|\
| *2dfdd705ffgit-p4.py: fix --prepare-p4-only error with multiple commits
The significant changes since the last round of discussion are:
1. A streaming version of the algorithm has been implemented. No longer is revs->limited, with all of its very serious drawbacks, required.
2. The commit->parents commit_list is no longer modified (amputated). Instead, a "principle child" is identified during a (heavily modified) indegree walk.
3. Per D. Stolee's suggestion, the output of child->parent edges are suppressed during graph emission (in particular, in graph_is_interesting).
4. No commit flags are used. All per-commit ancillary data is stored in a commit slab.
I discarded J. Sixt's suggestion to change the format of the --boundary output. While I like the proposed format, I think the change is orthogonal to this (already large) change.
There are several outstanding issues that I would appreciate help with:
1. I have developed some terminology to think about the concepts used here. They are definitely not conventional, and probably should be changed. I would appreciate feedback:
- A "skeleton walk" is the streaming version of a left-first DFS-generated spanning tree. This is achieved using a carefully generation-limited traversal of the commit graph. *Edges* are stored in a skel_walk_list structure. This traversal should be linear in the number of edges (but I'll admit I haven't actually done this proof).
- The "guide commits" are all of the commits in revs->commits.
- A "component" (and this is particularly bad terminology) is the collection of commits reachable from a guide commit, but not from an earlier ("higher priority") guide commit.
This approach avoids any ambiguity in the output of --ignore-merge-bases as to what commits are included at the merge point, by always drawing any edge between components. Notice that the definition of a component means that no edges go from higher- priority to lower-priority components (instead, those commits are absorbed into the higher-priority component).
- The "principle child" of a commit c is the first child in the leftmost-first DFS that references c. It is always in the same component as c, and it is the only commit in that component whose edge is drawn connecting to c.
Presumably, all of these terms should be documented (with visuals) somewhere. If there is serious interest in this patch, I'm happy to do this, but I'm loathe to waste time doing this until I start hearing some sort of positive feedback on what has become a significant time sink.
2. The meat of the changes are monolithically collected into patch 2/3. It does not make sense in my mind to implement functions that are not used anywhere, and then make first use them in another commit. But, I can split this up into the skeleton walk implementation and the graph display, if wanted.
3. A skel_walk_info structure is allocated at parameter parse time, and currently is never freed. While this is certainly a memory leak, it is not clear to me if there is a benefit to performing the cleanup, besides getting clean valgrind output (and masking more serious memory leaks). I I didn't try to read everything in Documentation, but, besides an abundance of commits fixing memory leaks, I could not find a specific policy regarding freeing memory before program termination.
4. The implementation for revs->limited and !revs->limited is frustratingly similar, but I cannot see any particular elegant way to deduplicate the code. The existing code also seems to suffer similarly.
Is there movement forward on eliminating the whole rev->limited code-path? This is obviously out of scope for this patch set, but maintaining two code-paths was a hassle for this one action, and I can imagine that it is much worse when multiplied by all of git's features.
5. Similarly, the skel_walk is very similar to the existing indegree walk. But again, avoiding duplicated code leads to uncomfortable
Quoted 3 lines
if (skel) {
...
}blocks. It also confuses gcc, which has trouble realizing that variables were initialized in previous if (skel) blocks. I'm then forced to resort to underhanded tricks: blanket initializing of variables that should have been optimized out if !skel.
Duplicating the entire function leads to cleaner and negligibly faster code. Frustratingly, but unsurprisingly, the meticulous careful skeleton walk that I've implemented is slightly slower than the existing indegree walk, so it's a bad candidate to replace the old code.
Any thoughts?
The entire patch set is also available at [1], which includes a few debugging assertions enabled, and the excision of the unused free_skel_info method (see 3, above) which otherwise breaks -Wunused-function. It passes the full battery of tests there (as well as locally for me).
Best,
Antonio Russo
PATCH 1/3 Clean up t6016-rev-list-graph-simplify-history
Simplifies the logic used to test rev-list, making adding new tests easier. Uses a heredoc and sed expansion of the expected output, instead of shell substitutions and manually escaped echo's.
--- t/t6016-rev-list-graph-simplify-history.sh | 350 ++++++++++----------- 1 file changed, 167 insertions(+), 183 deletions(-)
t/t6016-rev-list-graph-simplify-history.sh +167 -183
@@ -9,6 +9,13 @@ test_description='--graph and simplified history' . ./test-lib.sh +check_graph () { + sed -f expand_tag_to_oid.sed >expect && + git rev-list --graph "$@" >actual && + sed 's/ *$//' actual >actual.sanitized && + test_cmp expect actual.sanitized +} + test_expect_success 'set up rev-list --graph test' ' # 3 commits on branch A test_commit A1 foo.txt &&
@@ -43,76 +50,62 @@ test_expect_success 'set up rev-list --graph test' ' test_commit A7 bar.txt && - # Store commit names in variables for later use - A1=$(git rev-parse --verify A1) && - A2=$(git rev-parse --verify A2) && - A3=$(git rev-parse --verify A3) && - A4=$(git rev-parse --verify A4) && - A5=$(git rev-parse --verify A5) && - A6=$(git rev-parse --verify A6) && - A7=$(git rev-parse --verify A7) && - B1=$(git rev-parse --verify B1) && - B2=$(git rev-parse --verify B2) && - C1=$(git rev-parse --verify C1) && - C2=$(git rev-parse --verify C2) && - C3=$(git rev-parse --verify C3) && - C4=$(git rev-parse --verify C4) - ' + git for-each-ref --format="s/%(refname:short)/%(objectname)/" \ + refs/tags >expand_tag_to_oid.sed +' test_expect_success '--graph --all' ' - rm -f expected && - echo "* $A7" >> expected && - echo "* $A6" >> expected && - echo "|\\ " >> expected && - echo "| * $C4" >> expected && - echo "| * $C3" >> expected && - echo "* | $A5" >> expected && - echo "| | " >> expected && - echo "| \\ " >> expected && - echo "*-. | $A4" >> expected && - echo "|\\ \\| " >> expected && - echo "| | * $C2" >> expected && - echo "| | * $C1" >> expected && - echo "| * | $B2" >> expected && - echo "| * | $B1" >> expected && - echo "* | | $A3" >> expected && - echo "| |/ " >> expected && - echo "|/| " >> expected && - echo "* | $A2" >> expected && - echo "|/ " >> expected && - echo "* $A1" >> expected && - git rev-list --graph --all > actual && - test_cmp expected actual - ' + check_graph --all <<-\EOF + * A7 + * A6 + |\ + | * C4 + | * C3 + * | A5 + | | + | \ + *-. | A4 + |\ \| + | | * C2 + | | * C1 + | * | B2 + | * | B1 + * | | A3 + | |/ + |/| + * | A2 + |/ + * A1 + EOF +' # Make sure the graph_is_interesting() code still realizes # that undecorated merges are interesting, even with --simplify-by-decoration test_expect_success '--graph --simplify-by-decoration' ' - rm -f expected && git tag -d A4 && - echo "* $A7" >> expected && - echo "* $A6" >> expected && - echo "|\\ " >> expected && - echo "| * $C4" >> expected && - echo "| * $C3" >> expected && - echo "* | $A5" >> expected && - echo "| | " >> expected && - echo "| \\ " >> expected && - echo "*-. | $A4" >> expected && - echo "|\\ \\| " >> expected && - echo "| | * $C2" >> expected && - echo "| | * $C1" >> expected && - echo "| * | $B2" >> expected && - echo "| * | $B1" >> expected && - echo "* | | $A3" >> expected && - echo "| |/ " >> expected && - echo "|/| " >> expected && - echo "* | $A2" >> expected && - echo "|/ " >> expected && - echo "* $A1" >> expected && - git rev-list --graph --all --simplify-by-decoration > actual && - test_cmp expected actual - ' + check_graph --all --simplify-by-decoration <<-\EOF + * A7 + * A6 + |\ + | * C4 + | * C3 + * | A5 + | | + | \ + *-. | A4 + |\ \| + | | * C2 + | | * C1 + | * | B2 + | * | B1 + * | | A3 + | |/ + |/| + * | A2 + |/ + * A1 + EOF +' test_expect_success 'setup: get rid of decorations on B' ' git tag -d B2 &&
@@ -122,142 +115,133 @@ test_expect_success 'setup: get rid of decorations on B' ' # Graph with branch B simplified away test_expect_success '--graph --simplify-by-decoration prune branch B' ' - rm -f expected && - echo "* $A7" >> expected && - echo "* $A6" >> expected && - echo "|\\ " >> expected && - echo "| * $C4" >> expected && - echo "| * $C3" >> expected && - echo "* | $A5" >> expected && - echo "* | $A4" >> expected && - echo "|\\| " >> expected && - echo "| * $C2" >> expected && - echo "| * $C1" >> expected && - echo "* | $A3" >> expected && - echo "|/ " >> expected && - echo "* $A2" >> expected && - echo "* $A1" >> expected && - git rev-list --graph --simplify-by-decoration --all > actual && - test_cmp expected actual - ' + check_graph --simplify-by-decoration --all <<-\EOF + * A7 + * A6 + |\ + | * C4 + | * C3 + * | A5 + * | A4 + |\| + | * C2 + | * C1 + * | A3 + |/ + * A2 + * A1 + EOF +' test_expect_success '--graph --full-history -- bar.txt' ' - rm -f expected && - echo "* $A7" >> expected && - echo "* $A6" >> expected && - echo "|\\ " >> expected && - echo "| * $C4" >> expected && - echo "* | $A5" >> expected && - echo "* | $A4" >> expected && - echo "|\\| " >> expected && - echo "* | $A3" >> expected && - echo "|/ " >> expected && - echo "* $A2" >> expected && - git rev-list --graph --full-history --all -- bar.txt > actual && - test_cmp expected actual - ' + check_graph --full-history --all -- bar.txt <<-\EOF + * A7 + * A6 + |\ + | * C4 + * | A5 + * | A4 + |\| + * | A3 + |/ + * A2 + EOF +' test_expect_success '--graph --full-history --simplify-merges -- bar.txt' ' - rm -f expected && - echo "* $A7" >> expected && - echo "* $A6" >> expected && - echo "|\\ " >> expected && - echo "| * $C4" >> expected && - echo "* | $A5" >> expected && - echo "* | $A3" >> expected && - echo "|/ " >> expected && - echo "* $A2" >> expected && - git rev-list --graph --full-history --simplify-merges --all \ - -- bar.txt > actual && - test_cmp expected actual - ' + check_graph --full-history --simplify-merges --all -- bar.txt <<-\EOF + * A7 + * A6 + |\ + | * C4 + * | A5 + * | A3 + |/ + * A2 + EOF +' test_expect_success '--graph -- bar.txt' ' - rm -f expected && - echo "* $A7" >> expected && - echo "* $A5" >> expected && - echo "* $A3" >> expected && - echo "| * $C4" >> expected && - echo "|/ " >> expected && - echo "* $A2" >> expected && - git rev-list --graph --all -- bar.txt > actual && - test_cmp expected actual - ' + check_graph --all -- bar.txt <<-\EOF + * A7 + * A5 + * A3 + | * C4 + |/ + * A2 + EOF +' test_expect_success '--graph --sparse -- bar.txt' ' - rm -f expected && - echo "* $A7" >> expected && - echo "* $A6" >> expected && - echo "* $A5" >> expected && - echo "* $A4" >> expected && - echo "* $A3" >> expected && - echo "| * $C4" >> expected && - echo "| * $C3" >> expected && - echo "| * $C2" >> expected && - echo "| * $C1" >> expected && - echo "|/ " >> expected && - echo "* $A2" >> expected && - echo "* $A1" >> expected && - git rev-list --graph --sparse --all -- bar.txt > actual && - test_cmp expected actual - ' + check_graph --sparse --all -- bar.txt <<-\EOF + * A7 + * A6 + * A5 + * A4 + * A3 + | * C4 + | * C3 + | * C2 + | * C1 + |/ + * A2 + * A1 + EOF +' test_expect_success '--graph ^C4' ' - rm -f expected && - echo "* $A7" >> expected && - echo "* $A6" >> expected && - echo "* $A5" >> expected && - echo "* $A4" >> expected && - echo "|\\ " >> expected && - echo "| * $B2" >> expected && - echo "| * $B1" >> expected && - echo "* $A3" >> expected && - git rev-list --graph --all ^C4 > actual && - test_cmp expected actual - ' + check_graph --all ^C4 <<-\EOF + * A7 + * A6 + * A5 + * A4 + |\ + | * B2 + | * B1 + * A3 + EOF +' test_expect_success '--graph ^C3' ' - rm -f expected && - echo "* $A7" >> expected && - echo "* $A6" >> expected && - echo "|\\ " >> expected && - echo "| * $C4" >> expected && - echo "* $A5" >> expected && - echo "* $A4" >> expected && - echo "|\\ " >> expected && - echo "| * $B2" >> expected && - echo "| * $B1" >> expected && - echo "* $A3" >> expected && - git rev-list --graph --all ^C3 > actual && - test_cmp expected actual - ' + check_graph --all ^C3 <<-\EOF + * A7 + * A6 + |\ + | * C4 + * A5 + * A4 + |\ + | * B2 + | * B1 + * A3 + EOF +' # I don't think the ordering of the boundary commits is really # that important, but this test depends on it. If the ordering ever changes # in the code, we'll need to update this test. test_expect_success '--graph --boundary ^C3' ' - rm -f expected && - echo "* $A7" >> expected && - echo "* $A6" >> expected && - echo "|\\ " >> expected && - echo "| * $C4" >> expected && - echo "* | $A5" >> expected && - echo "| | " >> expected && - echo "| \\ " >> expected && - echo "*-. \\ $A4" >> expected && - echo "|\\ \\ \\ " >> expected && - echo "| * | | $B2" >> expected && - echo "| * | | $B1" >> expected && - echo "* | | | $A3" >> expected && - echo "o | | | $A2" >> expected && - echo "|/ / / " >> expected && - echo "o / / $A1" >> expected && - echo " / / " >> expected && - echo "| o $C3" >> expected && - echo "|/ " >> expected && - echo "o $C2" >> expected && - git rev-list --graph --boundary --all ^C3 > actual && - test_cmp expected actual - ' + check_graph --boundary --all ^C3 <<-\EOF + * A7 + * A6 + |\ + | * C4 + * | A5 + | | + | \ + *-. \ A4 + |\ \ \ + | * | | B2 + | * | | B1 + * | | | A3 + o | | | A2 + |/ / / + o / / A1 + / / + | o C3 + |/ + o C2 + EOF +' test_done
Signature · 1 line
2.27.0
Re: [PATCH 1/3] Clean up t6016-rev-list-graph-simplify-history
Quoted 1 line · Antonio Russo
Subject: Re: [PATCH 1/3] Clean up t6016-rev-list-graph-simplify-history
Hmph, didn't anybody give you guidance on the subjects the last round?
If this is a second round (I do not recall---I read too many patches), the subject should begin with
[PATCH v2 1/3]
and then "<area>: one line summary". For test scripts, the script number is enough to identify the area the patch affects, e.g.
[PATCH v2 1/3] t6016: simplify the way expected history is drawn
Quoted 3 lines
Simplifies the logic used to test rev-list, making adding new tests easier. Uses a heredoc and sed expansion of the expected output, instead of shell substitutions and manually escaped echo's.
Justify why this change is a good thing upfront, by (1) giving a short summary of what is done in the current code and (2) saying what is suboptimal in it.
Many tests in this script prepare each line of the expected --graph output separately with "echo", using bare object names of commits shown in the graph (captured in shell variables), run "rev-list --graph" with some other parameters and compares the result. The expected shape of the graph is hard to see and the resulting code is repetitious.
And then outline your solution, giving orders to the codebase to "become like so", in the next paragraph.
In order to add new tests easier, introduce a helper function that takes extra parameters given to the "rev-list --graph" as its arguments, and the expected output from its standard input stream. By allowing tagnames to be used in the expected output, eliminate the need to capture commit object names in shell variables.
cf. Documentation/SubmittingPatches::imperative-mood
Quoted 1 line
Reviewed-by Junio C Hamano <[email protected]>
I didn't review this version (in other words, I think you changed the patch after I reviewed)---so do not write this line. It is misleading.
t/t6016-rev-list-graph-simplify-history.sh test_description='--graph and simplified history' · line 17
Quoted 8 lines
. ./test-lib.sh
t/t6016-rev-list-graph-simplify-history.sh +6
-0+check_graph () { + sed -f expand_tag_to_oid.sed >expect && + git rev-list --graph "$@" >actual && + sed 's/ *$//' actual >actual.sanitized && + test_cmp expect actual.sanitized +}
OK, so we prepare the mapping from tagname to objectname somewhere, feed an expected output that uses tagname to this helper function and munge it into the file expect, and then compare it with the actual output.
Why do we drop the trailing whitespace in the output before comparing? Is it because it does not matter? Is it because it is cumbersome to spell in the expected output in the source?
Not complaining. But if we truly aim to make writing new tests easier, we should tell those who may write new tests what they are expected to be doing when using this helper function in a comment before it to help them. Some points I can think of off the top of my head are:
* The file expend_tag_to_oid.sed is created in a single "setup" test; when adding a new test, the shape of the history and new tags used in it must be prepared before the "for-each-ref" that produces the file in the "setup" test.
* The arguments to the helper are given to "git rev-list --graph" to be compared with the expected graph fed from the standard input.
* The expected graph can use tags and branches instead of object names (and it is encouraged to do so) for readability. You do not mimick trailing whitespaces on the lines [*1*].
Quoted 38 lines
test_expect_success'--graph --all' 't/t6016-rev-list-graph-simplify-history.sh +13
-24- rm -f expected && - echo "* $A7" >> expected && - echo "* $A6" >> expected && - echo "|\\ " >> expected && - echo "| * $C4" >> expected && - echo "| * $C3" >> expected && - echo "* | $A5" >> expected && - echo "| | " >> expected && - echo "| \\ " >> expected && - echo "*-. | $A4" >> expected && - echo "|\\ \\| " >> expected && - echo "| | * $C2" >> expected && - echo "| | * $C1" >> expected && - echo "| * | $B2" >> expected && - echo "| * | $B1" >> expected && - echo "* | | $A3" >> expected && - echo "| |/ " >> expected && - echo "|/| " >> expected && - echo "* | $A2" >> expected && - echo "|/ " >> expected && - echo "* $A1" >> expected && - git rev-list --graph --all > actual && - test_cmp expected actual - ' + check_graph --all <<-\EOF + * A7 + * A6 + |\ + | * C4 + | * C3 + * | A5 + | | + | \ + *-. | A4 + |\ \| + | | * C2 + | | * C1
t/t6016-rev-list-graph-simplify-history.sh test_expect_success 'set up rev-list --graph test' ' · line 80
Quoted 10 lines
t/t6016-rev-list-graph-simplify-history.sh +10
-0+ | * | B2 + | * | B1 + * | | A3 + | |/ + |/| + * | A2 + |/ + * A1 + EOF +'
I do agree that the resulting test is easier to understand.
Thanks.
[Footnote *1*]
This is a tangent, but I wonder if somebody looked into how feasible it is to eliminate the trailing whitespace in the graph output. It is OK to give whitespaces in anticipation of writing the commit object names, but on a line in the output that exists only to show connecting lines, where we know we will not write anything after the graph, there is no excuse to end the graph part with a trailing whitespace.
PATCH 2/3 Teach git-rev-list --ignore-merge-bases
In reply to Antonio RussoThis new option simplifies the graph of commits for merges. Edges to commits reachable from more leftward parents, or more leftward parents of recursive child commits, are removed. This "skeleton" spanning tree effectively omits all information about merge bases.
When multiple tip commits are specified, all commits reachable from each tip commit (but not earlier tips) are simplified as above to form a "component". All edges between components are displayed.
When used with --graph, this amputation can dramatically reduce the width of the displayed graph and the total time taken to draw all output.
--- Documentation/rev-list-options.txt | 13 ++ builtin/log.c | 2 +- builtin/show-branch.c | 2 +- commit.c | 132 +++++++++++++--- commit.h | 4 +- graph.c | 40 +++-- revision.c | 240 +++++++++++++++++++++++++++-- revision.h | 17 ++ 8 files changed, 404 insertions(+), 46 deletions(-)
Documentation/rev-list-options.txt +13 -0
@@ -363,6 +363,19 @@ Default mode:: merges from the resulting history, as there are no selected commits contributing to this merge. +--ignore-merge-bases:: + Simplify merges by removing edges to commits reachable from + more leftware parents, or more leftward parents of recursive + children. When used with `--graph`, this can help visualize + repositories with many merges when you are not interested in + the merge base used for each merge. It also reduces the width + of the graph visualization when used with `--graph`. + + When multiple tip commits are specified, all commits reachable + from each tip commit (but not earlier tips) are simplified as + above to form a "component". All edges between components are + displayed. + --ancestry-path:: When given a range of commits to display (e.g. 'commit1..commit2' or 'commit2 {caret}commit1'), only display commits that exist
builtin/log.c +1 -1
@@ -306,7 +306,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)int show_header =1 ; revs->diffopt.close_file =0 ; -sort_in_topological_order (&list, revs->sort_order); +sort_in_topological_order (&list,NULL , revs->sort_order);while (list && i) {struct commit *commit = list->item;switch (simplify_commit (revs, commit)) {
builtin/show-branch.c +1 -1
@@ -903,7 +903,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)exit (0 );/* Sort topologically */ -sort_in_topological_order (&seen, sort_order); +sort_in_topological_order (&seen,NULL , sort_order);/* Give names to commits */ if (!sha1_name && !no_name)
commit.c +110 -22
182 lines not on this page · raw message
commit.h +3 -1
@@ -183,6 +183,7 @@ struct commit_list *copy_commit_list(struct commit_list *list);void free_commit_list (struct commit_list *list);struct rev_info ;/* in revision.h, it circularly uses enum cmit_fmt */ +struct skel_info ;int has_non_ascii (const char *text); const char *logmsg_reencode(const struct commit *commit,
@@ -226,7 +227,8 @@ enum rev_sort_order {* chain together. * REV_SORT_BY_COMMIT_DATE: show eligible commits in committer-date order. */ -void sort_in_topological_order (struct commit_list **,enum rev_sort_order ); +void sort_in_topological_order (struct commit_list **,struct skel_info *, +enum rev_sort_order );struct commit_graft {struct object_id oid;
graph.c +31 -9
@@ -428,21 +428,43 @@ static void graph_ensure_capacity(struct git_graph *graph, int num_columns)*/ static int graph_is_interesting (struct git_graph *graph,struct commit *commit) { -/* -* If revs->boundary is set, commits whose children have -* been shown are always interesting, even if they have the -* UNINTERESTING or TREESAME flags set. -*/ -if (graph->revs && graph->revs->boundary) { -if (commit->object.flags &CHILD_SHOWN ) -return 1 ; +struct skel_datum *dat_p, *dat_c; +struct rev_info *revs = graph->revs; +struct skel_info *skel =NULL ; + +if (revs->ignore_merge_bases) + skel = revs->skel_info; + +if (revs) { +/* +* If revs->boundary is set, commits whose children have +* been shown are always interesting, even if they have the +* UNINTERESTING or TREESAME flags set. +*/ +if (revs->boundary) { +if (commit->object.flags &CHILD_SHOWN ) +return 1 ; + } + +/* +* If revs->ignore_merge_bases is set, suppress intra-component +* edges that are not from the principle child. +*/ +if (skel) { + dat_p =skel_slab_at (&skel->slab, commit); + dat_c =skel_slab_at (&skel->slab, graph->commit); +if (dat_p->component == dat_c->component && + dat_p->child != graph->commit) { +return 0 ; + } + } }/* * Otherwise, use get_commit_action() to see if this commit is * interesting */ -return get_commit_action (graph->revs, commit) == commit_show; +return get_commit_action (revs, commit) == commit_show; } static struct commit_list *next_interesting_parent(struct git_graph *graph,
revision.c +228 -12
315 lines not on this page · raw message
revision.h +17 -0
@@ -88,6 +88,21 @@ struct rev_cmdline_info {struct oidset ;struct topo_walk_info ; +struct skel_datum { +int component; +struct commit *child; +}; + +define_shared_commit_slab(skel_slab, struct skel_datum); + +struct skel_walk_list ; + +struct skel_info { +struct skel_walk_list *walk; +int next_comp; +struct skel_slab slab; +}; +struct rev_info {/* Starting list */ struct commit_list *commits;
@@ -137,6 +152,7 @@ struct rev_info { show_pulls:1, topo_order:1, simplify_merges:1, + ignore_merge_bases:1, simplify_by_decoration:1, single_worktree:1, tag_objects:1,
@@ -307,6 +323,7 @@ struct rev_info {* This is loaded from the commit-graph being used. */ struct bloom_filter_settings *bloom_filter_settings; +struct skel_info *skel_info; };int ref_excluded (struct string_list *,const char *path);
Signature · 1 line
2.27.0
PATCH 3/3 Add new tests of --ignore-merge-bases
In reply to Antonio RussoExtend t4215 and t6016 to also use --ignore-merge-bases on their test cases.
Add the new test case t4217-log-merges, with three tests: a standard feature merge, a "twisted" feature merge, and the motivating case for
ignore-merge-bases: a "mountain" of merges.
--- t/t4215-log-skewed-merges.sh | 169 +++++++++++++ t/t4217-log-merges.sh | 273 +++++++++++++++++++++ t/t6016-rev-list-graph-simplify-history.sh | 70 ++++++ 3 files changed, 512 insertions(+) create mode 100755 t/t4217-log-merges.sh
t/t4215-log-skewed-merges.sh +169 -0
@@ -38,6 +38,22 @@ test_expect_success 'log --graph with merge fusing with its left and right neigh EOF ' +test_expect_success 'log --graph with merge fusing with its left and right neighbors (ignore-merge-bases)' ' + check_graph --ignore-merge-bases <<-\EOF + * H + |\ + | * G + | |\ + | | * F + | * E + | |\ + | | * D + | * C + * B + * A + EOF +' + test_expect_success 'log --graph with left-skewed merge' ' git checkout --orphan 0_p && test_commit 0_A && git checkout -b 0_q 0_p && test_commit 0_B &&
@@ -72,6 +88,20 @@ test_expect_success 'log --graph with left-skewed merge' ' EOF ' +test_expect_success 'log --graph with left-skewed merge (ignore-merge-bases)' ' + check_graph --ignore-merge-bases <<-\EOF + *-----. 0_H + |\ \ \ \ + | | | | * 0_G + | | | * 0_F + | | | * 0_E + | | * 0_D + | | * 0_C + | * 0_B + * 0_A + EOF +' + test_expect_success 'log --graph with nested left-skewed merge' ' git checkout --orphan 1_p && test_commit 1_A &&
@@ -100,6 +130,21 @@ test_expect_success 'log --graph with nested left-skewed merge' ' EOF ' +test_expect_success 'log --graph with nested left-skewed merge (ignore-merge-bases)' ' + check_graph --ignore-merge-bases<<-\EOF + * 1_H + |\ + | * 1_G + | |\ + | | * 1_F + | * 1_E + | * 1_D + * 1_C + * 1_B + * 1_A + EOF +' + test_expect_success 'log --graph with nested left-skewed merge following normal merge' ' git checkout --orphan 2_p && test_commit 2_A &&
@@ -137,6 +182,23 @@ test_expect_success 'log --graph with nested left-skewed merge following normal EOF ' +test_expect_success 'log --graph with nested left-skewed merge following normal merge (ignore-merge-bases)' ' + check_graph --ignore-merge-bases<<-\EOF + * 2_K + |\ + | * 2_J + | |\ + | | * 2_H + | | * 2_G + | | * 2_F + | * 2_E + | * 2_D + * 2_C + * 2_B + * 2_A + EOF +' + test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge' ' git checkout --orphan 3_p && test_commit 3_A &&
@@ -170,6 +232,23 @@ test_expect_success 'log --graph with nested right-skewed merge following left-s EOF ' +test_expect_success 'log --graph with nested right-skewed merge following left-skewed merge (ignore-merge-bases)' ' + check_graph --ignore-merge-bases<<-\EOF + * 3_J + |\ + | * 3_H + | |\ + | | * 3_G + | * 3_F + | * 3_E + | |\ + | | * 3_D + | * 3_C + | * 3_B + * 3_A + EOF +' + test_expect_success 'log --graph with right-skewed merge following a left-skewed one' ' git checkout --orphan 4_p && test_commit 4_A &&
@@ -202,6 +281,23 @@ test_expect_success 'log --graph with right-skewed merge following a left-skewed EOF ' +test_expect_success 'log --graph with right-skewed merge following a left-skewed one (ignore-merge-bases)' ' + check_graph --date-order --ignore-merge-bases<<-\EOF + * 4_H + |\ + | * 4_G + | |\ + | * | 4_F + | * | 4_E + | |\ \ + | | * | 4_D + | | / + | | * 4_C + | * 4_B + * 4_A + EOF +' + test_expect_success 'log --graph with octopus merge with column joining its penultimate parent' ' git checkout --orphan 5_p && test_commit 5_A &&
@@ -239,6 +335,21 @@ test_expect_success 'log --graph with octopus merge with column joining its penu EOF ' +test_expect_success 'log --graph with octopus merge with column joining its penultimate parent (ignore-merge-bases)' ' + check_graph --ignore-merge-bases<<-\EOF + * 5_H + |\ + | *-. 5_G + | |\ \ + | | | * 5_F + | | * 5_E + | | * 5_C + | * 5_B + * 5_D + * 5_A + EOF +' + test_expect_success 'log --graph with multiple tips' ' git checkout --orphan 6_1 && test_commit 6_A &&
@@ -281,6 +392,29 @@ test_expect_success 'log --graph with multiple tips' ' EOF ' +test_expect_success 'log --graph with multiple tips (ignore-merge-bases)' ' + check_graph --ignore-merge-bases 6_1 6_3 6_5 <<-\EOF + * 6_I + |\ + | | * 6_H + | | |\ + | | | * 6_G + | | * | 6_E + | | | | * 6_F + | |_|_|/| + |/| | |/ + | | |/| + | |/| | + | * | | 6_D + | / / + * / / 6_C + |/ / + * / 6_B + |/ + * 6_A + EOF +' + test_expect_success 'log --graph with multiple tips and colors' ' test_config log.graphColors red,green,yellow,blue,magenta,cyan && cat >expect.colors <<-\EOF &&
@@ -370,4 +504,39 @@ test_expect_success 'log --graph with multiple tips' ' EOF ' +test_expect_success 'log --graph with multiple tips (ignore-merge-bases)' ' + check_graph --ignore-merge-bases M_1 M_3 M_5 M_7 <<-\EOF + * 7_M1 + |\ + | | * 7_M2 + | | |\ + | | | * 7_H + | | | | * 7_M3 + | | | | |\ + | | | | | * 7_J + | | | | * | 7_I + | | | | | | * 7_M4 + | |_|_|_|_|/|\ + |/| | | | |/ / + | | |_|_|/| / + | |/| | | |/ + | | | |_|/| + | | |/| | | + | | * | | | 7_G + | | | |_|/ + | | |/| | + | | * | | 7_F + | * | | | 7_E + | | |/ / + | |/| | + | * | | 7_D + | / / + * / / 7_C + |/ / + * / 7_B + |/ + * 7_A + EOF +' + test_done
t/t4217-log-merges.sh new file +273 -0
273 lines not on this page · raw message
t/t6016-rev-list-graph-simplify-history.sh +70 -0
92 lines not on this page · raw message
Signature · 1 line
2.27.0