| Message ID | d3079ba8-33e1-3b68-23d2-ea97b9ca1e97@gmail.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | [v2] Teach git-rev-list --simplify-forks | expand |
Hi Antonio, On 29/04/2020 09:01, Antonio Russo wrote: > When used with --graph, instead of displaying the full graph, display a > spanning subgraph produced by a depth-first search of the graph visiting > parents from left to right. Edges to already visited commits are > discarded. This process is repeated for every commit to be displayed. > > This is valuable to reduce visual clutter when there are many merges > that were not rebased onto each other and the user is primarily > interested in the state of the branch being merged into. > > Also adds documentation and tests of the above. > > Signed-off-by: Antonio Russo <antonio.e.russo@gmail.com> > --- > Documentation/rev-list-options.txt | 8 +++ > revision.c | 62 ++++++++++++++++++++++ > revision.h | 6 +++ > t/t6016-rev-list-graph-simplify-history.sh | 50 +++++++++++++++++ > 4 files changed, 126 insertions(+) > > Hello, > > This second revision of the patch sets revs->limited. This forces the > graph of commits to be loaded, and simplfiy_forks() therefore reliably > traverses it. This addresses the test failures mentioned before (see [1]). > > Antonio > > [1] https://travis-ci.org/github/aerusso/git/builds/680894920 > > diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt > index 04ad7dd36e..cbac09028c 100644 > --- a/Documentation/rev-list-options.txt > +++ b/Documentation/rev-list-options.txt > @@ -363,6 +363,14 @@ Default mode:: > merges from the resulting history, as there are no selected > commits contributing to this merge. > > +--simplify-forks:: > + Convert the commit graph into a spanning subgraph produced by a > + depth-first-search of the history graph, searching the leftmost > + parent first, and discarding edges to commits already visited. > + Useful with `--graph` to visualize repositories with many merges > + when you are interested in was added to master, and not when the > + branch was last rebased. Does this also need to actually mention that it effectively discard edges to fork points, as per the option name?. No rebasing required for it to be useful. s/when/where/ "...and not where the branch was last rebased or forked from." - not great but actually mentions the option. -- Philip > + > --ancestry-path:: > When given a range of commits to display (e.g. 'commit1..commit2' > or 'commit2 {caret}commit1'), only display commits that exist > diff --git a/revision.c b/revision.c > index 5bc96444b6..51dbe21847 100644 > --- a/revision.c > +++ b/revision.c > @@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg > revs->simplify_by_decoration = 1; > revs->limited = 1; > revs->prune = 1; > + } else if (!strcmp(arg, "--simplify-forks")) { > + revs->limited = 1; > + revs->simplify_forks = 1; > } else if (!strcmp(arg, "--date-order")) { > revs->sort_order = REV_SORT_BY_COMMIT_DATE; > revs->topo_order = 1; > @@ -3095,6 +3098,63 @@ static void simplify_merges(struct rev_info *revs) > } > } > > +static void simplify_forks(struct rev_info *revs) > +{ > + struct commit_list *stack, *list_lr, *iter_list; > + struct commit_list **parents; > + struct commit *commit, *parent; > + > + stack = NULL; > + list_lr = NULL; > + > + clear_object_flags(SIMP_FORK_VISITED); > + > + for(iter_list = revs->commits; iter_list; iter_list = iter_list->next) { > + /* process every commit to be displayed exactly once */ > + if(iter_list->item->object.flags & SIMP_FORK_VISITED) > + continue; > + clear_object_flags(SIMP_FORK_VISITING); > + commit_list_insert(iter_list->item, &stack); > + iter_list->item->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING; > + while(stack) { > + commit = pop_commit(&stack); > + /* process the parent nodes: removing links to > + * commits already visited (creating a spanning tree) > + */ > + parents = &(commit->parents); > + while(*parents) { > + parent = (*parents)->item; > + if(parent->object.flags & SIMP_FORK_VISITING) { > + /* We have already visited this commit, from the same root. > + * We do not explore it at all. > + */ > + pop_commit(parents); > + } else if(parent->object.flags & SIMP_FORK_VISITED) { > + /* We visited this commit before, but from a different root. > + * Leave it attached, but do not explore it further. > + */ > + parents = &((*parents)->next); > + } else { > + /* We have not visited this commit yet. Explore it, as usual. > + */ > + parent->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING; > + commit_list_insert(parent, &list_lr); > + parents = &((*parents)->next); > + } > + } > + > + /* feed the parents, right to left (reversed) onto the > + * stack to do a depth-first traversal of the commit graph > + */ > + while(list_lr) { > + commit_list_insert(pop_commit(&list_lr), &stack); > + } > + } > + } > + > + clear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING); > +} > + > static void set_children(struct rev_info *revs) > { > struct commit_list *l; > @@ -3392,6 +3452,8 @@ int prepare_revision_walk(struct rev_info *revs) > if (revs->limited) { > if (limit_list(revs) < 0) > return -1; > + if (revs->simplify_forks) > + simplify_forks(revs); > if (revs->topo_order) > sort_in_topological_order(&revs->commits, revs->sort_order); > } else if (revs->topo_order) > diff --git a/revision.h b/revision.h > index c1af164b30..f1abdb26b0 100644 > --- a/revision.h > +++ b/revision.h > @@ -51,6 +51,11 @@ > #define TOPO_WALK_EXPLORED (1u<<27) > #define TOPO_WALK_INDEGREE (1u<<28) > > +/* Re-use the TOPO_WALK flagspace for simplify_forks > + */ > +#define SIMP_FORK_VISITED (1u<<27) > +#define SIMP_FORK_VISITING (1u<<28) > + > #define DECORATE_SHORT_REFS 1 > #define DECORATE_FULL_REFS 2 > > @@ -132,6 +137,7 @@ struct rev_info { > no_walk:2, > remove_empty_trees:1, > simplify_history:1, > + simplify_forks:1, > show_pulls:1, > topo_order:1, > simplify_merges:1, > diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh > index f5e6e92f5b..d99214b6df 100755 > --- a/t/t6016-rev-list-graph-simplify-history.sh > +++ b/t/t6016-rev-list-graph-simplify-history.sh > @@ -85,6 +85,28 @@ test_expect_success '--graph --all' ' > test_cmp expected actual > ' > > +# Make sure that simplify_histpry_forks produces a spanning tree > +test_expect_success '--graph --simplify-forks --all' ' > + rm -f expected && > + echo "* $A7" >> expected && > + echo "* $A6" >> expected && > + echo "|\ " >> expected && > + echo "| * $C4" >> expected && > + echo "| * $C3" >> expected && > + echo "* $A5" >> expected && > + echo "*-. $A4" >> expected && > + echo "|\ \ " >> expected && > + echo "| | * $C2" >> expected && > + echo "| | * $C1" >> expected && > + echo "| * $B2" >> expected && > + echo "| * $B1" >> expected && > + echo "* $A3" >> expected && > + echo "* $A2" >> expected && > + echo "* $A1" >> expected && > + git rev-list --graph --simplify-forks --all > actual && > + test_cmp expected actual > + ' > + > # Make sure the graph_is_interesting() code still realizes > # that undecorated merges are interesting, even with --simplify-by-decoration > test_expect_success '--graph --simplify-by-decoration' ' > @@ -157,6 +179,20 @@ test_expect_success '--graph --full-history -- bar.txt' ' > test_cmp expected actual > ' > > +test_expect_success '--graph --simplify-forks --full-history -- bar.txt' ' > + rm -f expected && > + echo "* $A7" >> expected && > + echo "* $A6" >> expected && > + echo "|\\ " >> expected && > + echo "| * $C4" >> expected && > + echo "* $A5" >> expected && > + echo "* $A4" >> expected && > + echo "* $A3" >> expected && > + echo "* $A2" >> expected && > + git rev-list --graph --simplify-forks --full-history --all -- bar.txt > actual && > + test_cmp expected actual > + ' > + > test_expect_success '--graph --full-history --simplify-merges -- bar.txt' ' > rm -f expected && > echo "* $A7" >> expected && > @@ -172,6 +208,20 @@ test_expect_success '--graph --full-history --simplify-merges -- bar.txt' ' > test_cmp expected actual > ' > > +test_expect_success '--graph --simplify-forks --full-history --simplify-merges -- bar.txt' ' > + rm -f expected && > + echo "* $A7" >> expected && > + echo "* $A6" >> expected && > + echo "|\\ " >> expected && > + echo "| * $C4" >> expected && > + echo "* $A5" >> expected && > + echo "* $A3" >> expected && > + echo "* $A2" >> expected && > + git rev-list --graph --simplify-forks --full-history --simplify-merges --all \ > + -- bar.txt > actual && > + test_cmp expected actual > + ' > + > test_expect_success '--graph -- bar.txt' ' > rm -f expected && > echo "* $A7" >> expected &&
On 4/29/20 4:08 AM, Philip Oakley wrote: >> +--simplify-forks:: >> + Convert the commit graph into a spanning subgraph produced by a >> + depth-first-search of the history graph, searching the leftmost >> + parent first, and discarding edges to commits already visited. >> + Useful with `--graph` to visualize repositories with many merges >> + when you are interested in was added to master, and not when the >> + branch was last rebased. > > Does this also need to actually mention that it effectively discard > edges to fork points, as per the option name?. No rebasing required for > it to be useful. > s/when/where/ > "...and not where the branch was last rebased or forked from." - not > great but actually mentions the option. > > -- > Philip Good point. More generally, my description of the option is not very useful unless you already basically understand what it's doing. How about: > --simplify-forks:: > Omits the parent relationship of the first commit of merged branches. > Effectively discards all information about the fork point of merged > branches. It does so by converting the commit graph into a > spanning subgraph produced by a depth-first-search of the history > graph, searching the leftmost parent first, and discarding edges > to commits already visited. Useful with `--graph` to visualize > repositories with many merges when you are most interested in > when branches were merged. Antonio
On 4/29/2020 4:01 AM, Antonio Russo wrote: > When used with --graph, instead of displaying the full graph, display a > spanning subgraph produced by a depth-first search of the graph visiting > parents from left to right. Edges to already visited commits are > discarded. This process is repeated for every commit to be displayed. > > This is valuable to reduce visual clutter when there are many merges > that were not rebased onto each other and the user is primarily > interested in the state of the branch being merged into. My earlier comment to recommend how to fix the test failures intended to demonstrate that this area of code requires a bit of precision. I took some time to review this patch, but I find it needs some significant updates. tl;dr: The way you manipulate the commit parents seems incorrect to me, but perhaps there is enough prior art in the way we simplify parents to make that acceptable. Someone else will need to chime in on that part. It may be possible to do this "drop edges" entirely inside of graph.c (the graph rendering code) instead of revision.c, which would automatically work with the performance gains from the newer topo-walk algorithm. There are enough deviations from code and test style that this will need a significant revision regardless. > This second revision of the patch sets revs->limited. This forces the > graph of commits to be loaded, and simplfiy_forks() therefore reliably > traverses it. This addresses the test failures mentioned before (see [1]). This will have a significant performance impact on the option, as you will not see even the first result until the DFS has completed. > diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt > index 04ad7dd36e..cbac09028c 100644 > --- a/Documentation/rev-list-options.txt > +++ b/Documentation/rev-list-options.txt > @@ -363,6 +363,14 @@ Default mode:: > merges from the resulting history, as there are no selected > commits contributing to this merge. > > +--simplify-forks:: > + Convert the commit graph into a spanning subgraph produced by a > + depth-first-search of the history graph, searching the leftmost > + parent first, and discarding edges to commits already visited. > + Useful with `--graph` to visualize repositories with many merges > + when you are interested in was added to master, and not when the > + branch was last rebased. Describing the option via the algorithm may not be the best way to inform the user of what they will see. It also will not be informative if the implementation changes to not perform the algorithm described here, because that algorithm is not incremental (it is O(N) where N is the total number of reachable commits, not ~O(n) where n is the number of commits that will actually show up). An easy test is to time your command with "-n 1". I'm also not crazy about "when the branch was last rebased". You probably mean "..when you are not interested in which merge base was used for each merge." Also, this does nothing without "--graph" right? Perhaps it should enable it? Here is a suggested alternative: --simplify-forks:: Show commits that are introduced by each merge before showing the first parent of the merge, as in `--graph`, but remove edges from those commits to commits reachable from the first parent. This helps to visualize repositories with many merges when you are not interested in which merge base was used for each merge. It also reduces the width of the graph visualization compared to `--graph`. With this description, perhaps it is worth renaming the option? Perhaps "--ignore-merge-bases"? The word "simplify" implies something like dropping commits from history, but you are instead dropping _edges_ from the graph. > --ancestry-path:: > When given a range of commits to display (e.g. 'commit1..commit2' > or 'commit2 {caret}commit1'), only display commits that exist > diff --git a/revision.c b/revision.c > index 5bc96444b6..51dbe21847 100644 > --- a/revision.c > +++ b/revision.c > @@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg > revs->simplify_by_decoration = 1; > revs->limited = 1; > revs->prune = 1; > + } else if (!strcmp(arg, "--simplify-forks")) { > + revs->limited = 1; > + revs->simplify_forks = 1; I recommend dropping the revs->limited setting here and instead fixing the performance instead. But maybe that should be a second patch on top of this one. > } else if (!strcmp(arg, "--date-order")) { > revs->sort_order = REV_SORT_BY_COMMIT_DATE; > revs->topo_order = 1; > @@ -3095,6 +3098,63 @@ static void simplify_merges(struct rev_info *revs) > } > } > > +static void simplify_forks(struct rev_info *revs) > +{ > + struct commit_list *stack, *list_lr, *iter_list; > + struct commit_list **parents; You want "struct commit_list *parents" here for simpler use. > + struct commit *commit, *parent; > + > + stack = NULL; > + list_lr = NULL; > + > + clear_object_flags(SIMP_FORK_VISITED); > + > + for(iter_list = revs->commits; iter_list; iter_list = iter_list->next) { This method could use a split into at least two. I count three levels of nested loops here, so please break them up into smaller methods. > + /* process every commit to be displayed exactly once */ > + if(iter_list->item->object.flags & SIMP_FORK_VISITED) > + continue; > + clear_object_flags(SIMP_FORK_VISITING); This drops the flag from all commits. This will cause quadratic performance if combined with "--all". Drop this and instead clear the flag yourself as you visit commits. > + commit_list_insert(iter_list->item, &stack); > + iter_list->item->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING; > + while(stack) { > + commit = pop_commit(&stack); > + /* process the parent nodes: removing links to > + * commits already visited (creating a spanning tree) > + */ > + parents = &(commit->parents); > + while(*parents) { You have some whitespace issues. Put a space between "while" and "(". Same with "if"s below. > + parent = (*parents)->item; > + if(parent->object.flags & SIMP_FORK_VISITING) { > + /* We have already visited this commit, from the same root. > + * We do not explore it at all. > + */ > + pop_commit(parents); I don't think you want pop_commit() here. You want to have "parents = parents->next" at the end. Now, if this is how you are "simplifying" the edges in the final output, then I think this is destructive and unsafe! You are literally modifying "commit->parents" so if another operation in Git tries to read those parents it will see the wrong data. Think about a different way to achieve your goal here, perhaps in the rendering portion of graph.c instead of here. > + } else if(parent->object.flags & SIMP_FORK_VISITED) { > + /* We visited this commit before, but from a different root. > + * Leave it attached, but do not explore it further. > + */ > + parents = &((*parents)->next); > + } else { > + /* We have not visited this commit yet. Explore it, as usual. > + */ > + parent->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING; > + commit_list_insert(parent, &list_lr); > + parents = &((*parents)->next); > + } It is very unclear that your loop terminates. Instead, use "parents = parents->next" at the end of the loop block to make is extremely clear that the loop behaves as expected. Of course, this assumes that you are not being destructive to the commit parents as you explore. > + } > + > + /* feed the parents, right to left (reversed) onto the > + * stack to do a depth-first traversal of the commit graph > + */ nit: multi-line comment style [1] [1] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L285-L291 > + while(list_lr) { > + commit_list_insert(pop_commit(&list_lr), &stack); > + } nit: No curly braces around single-line blocks. [2] [2] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L239-L243 > + } > + } > + > + clear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING); > +} > + > static void set_children(struct rev_info *revs) > { > struct commit_list *l; > @@ -3392,6 +3452,8 @@ int prepare_revision_walk(struct rev_info *revs) > if (revs->limited) { > if (limit_list(revs) < 0) > return -1; > + if (revs->simplify_forks) > + simplify_forks(revs); > if (revs->topo_order) > sort_in_topological_order(&revs->commits, revs->sort_order); > } else if (revs->topo_order) > diff --git a/revision.h b/revision.h > index c1af164b30..f1abdb26b0 100644 > --- a/revision.h > +++ b/revision.h > @@ -51,6 +51,11 @@ > #define TOPO_WALK_EXPLORED (1u<<27) > #define TOPO_WALK_INDEGREE (1u<<28) > > +/* Re-use the TOPO_WALK flagspace for simplify_forks > + */ > +#define SIMP_FORK_VISITED (1u<<27) > +#define SIMP_FORK_VISITING (1u<<28) I don't like that you are re-using these, as it is dangerous for later collisions. At the moment, these flags are not used in the same code paths because you specify "limited = 1" and that code path does not use TOPO_WALK_* macros. > #define DECORATE_SHORT_REFS 1 > #define DECORATE_FULL_REFS 2 > > @@ -132,6 +137,7 @@ struct rev_info { > no_walk:2, > remove_empty_trees:1, > simplify_history:1, > + simplify_forks:1, > show_pulls:1, > topo_order:1, > simplify_merges:1, > diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh > index f5e6e92f5b..d99214b6df 100755 > --- a/t/t6016-rev-list-graph-simplify-history.sh > +++ b/t/t6016-rev-list-graph-simplify-history.sh > @@ -85,6 +85,28 @@ test_expect_success '--graph --all' ' > test_cmp expected actual > ' > > +# Make sure that simplify_histpry_forks produces a spanning tree > +test_expect_success '--graph --simplify-forks --all' ' > + rm -f expected && > + echo "* $A7" >> expected && > + echo "* $A6" >> expected && > + echo "|\ " >> expected && > + echo "| * $C4" >> expected && > + echo "| * $C3" >> expected && > + echo "* $A5" >> expected && > + echo "*-. $A4" >> expected && > + echo "|\ \ " >> expected && > + echo "| | * $C2" >> expected && > + echo "| | * $C1" >> expected && > + echo "| * $B2" >> expected && > + echo "| * $B1" >> expected && > + echo "* $A3" >> expected && > + echo "* $A2" >> expected && > + echo "* $A1" >> expected && Do not use too many echos like this. Instead use t4215-log-skewed-merges.sh as an example [3]. [3] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/t/t4215-log-skewed-merges.sh#L24-L37 I also hope that you can find more complicated cases to test, including: 1. A merge that brings in a merge (think a feature branch) 2. A merge that brings in a twisted merge (think a user using "git pull"). Here are some example --graph and --simplify-forks outputs to try. I have not tested these myself, but I believe they are interesting test cases that can trip up other algorithms. Merge bringing a merge (non-twisted): --graph --simplify-forks * * |\ |\ | * | * | |\ | |\ | | * | | * | * | | * * | | * |/ / * * / * |/ * Twisted merge: --graph --simplify-forks * * |\ |\ | * | * | |\ | * | * | * | | | * * |/ * |/| * | |/ * Thanks, -Stolee
On 4/29/20 7:12 AM, Derrick Stolee wrote: > On 4/29/2020 4:01 AM, Antonio Russo wrote: >> When used with --graph, instead of displaying the full graph, display a >> spanning subgraph produced by a depth-first search of the graph visiting >> parents from left to right. Edges to already visited commits are >> discarded. This process is repeated for every commit to be displayed. >> >> This is valuable to reduce visual clutter when there are many merges >> that were not rebased onto each other and the user is primarily >> interested in the state of the branch being merged into. > > My earlier comment to recommend how to fix the test failures intended > to demonstrate that this area of code requires a bit of precision. I > took some time to review this patch, but I find it needs some significant > updates. > > tl;dr: The way you manipulate the commit parents seems incorrect to me, > but perhaps there is enough prior art in the way we simplify parents to > make that acceptable. Someone else will need to chime in on that part. First, thank you for taking the time look at this. I understand your hesitation about the "amputation" of the history, but in some sense that's the point of this option. I really want to be ignorant of the details of when the fork branched off. I would like the reported history to be appear nearly equivalent to a rebase-and-fastforward only merge style, which results in a much simpler git log --graph. > It may be possible to do this "drop edges" entirely inside of graph.c > (the graph rendering code) instead of revision.c, which would automatically > work with the performance gains from the newer topo-walk algorithm. Non-local information about the commit graph needs to be used to do this amputation of the history. We cannot know how many parents we want to display until we've completely explored all the parents of that node. Unfortunately, that means that the whole graph needs to be loaded, and I cannot really see how there would be any gain by doing this in graph.c. Caveat: there are semi-streaming DFS implementations (i.e., O(n log n) space) that we might be able to use to get the first line out the door quicker. I would, however, like to leave that to another patch. I will also add that, for the tests I've done, all performance penalties have been insignificant (less than ~5% for showing the first commit), while there are significant performance _improvements_, e.g., ~40% for displaying the full tree. A notable exception is --all, which can be ~50x faster for the full output, but is often dramatically slower to show anything (i.e., the first line). > There are enough deviations from code and test style that this will > need a significant revision regardless. (Please see forthcoming revision 3). >> This second revision of the patch sets revs->limited. This forces the >> graph of commits to be loaded, and simplfiy_forks() therefore reliably >> traverses it. This addresses the test failures mentioned before (see [1]). > > This will have a significant performance impact on the option, as you will > not see even the first result until the DFS has completed. First of all, short of using some other, more sophisticated streaming version of this algorithm, the full DFS must finish before the first commit having two (or more) parents can be shown. That said, the performance is not significantly affected: I ran the following test (2.26.2, with my patch on top of it): (git lg = git log --graph --pretty=oneline) % time git lg -n1 --ignore-merge-bases e896a286df > /dev/null 0.73s user 0.02s system 99% cpu 0.746 total % time git lg -n1 e896a286df > /dev/null 0.72s user 0.01s system 99% cpu 0.731 total For the linux git repo: % time git lg -n1 --ignore-merge-bases v5.7-rc3 >/dev/null 9.25s user 0.39s system 99% cpu 9.646 total % time git lg -n1 v5.7-rc3 >/dev/null 9.02s user 0.35s system 99% cpu 9.378 total So the performance seems basically unaffected for very limited graphs. It's also about 40% faster for complicated ones (as mentioned in my first email): % time git lg --ignore-merge-bases e870325ee8 > /dev/null 0.83s user 0.06s system 99% cpu 0.886 total % time git lg e870325ee8 > /dev/null 1.41s user 0.03s system 99% cpu 1.443 total For the linux git repo: % time git lg --ignore-merge-bases v5.7-rc3 >/dev/null 11.86s user 0.62s system 99% cpu 12.489 total % time git lg v5.7-rc3 >/dev/null 21.56s user 0.55s system 99% cpu 22.108 total This is because the amputated graph is much simpler, and the rest of the code needs to do much less work. Passing --all is another beast, and does indeed suffer: % time git lg --ignore-merge-bases --all >/dev/null 4.06s user 0.04s system 99% cpu 4.105 total % time git lg --all >/dev/null 189.59s user 0.04s system 99% cpu 3:09.65 total (and for the first line) % time git lg -n1 --ignore-merge-bases --all >/dev/null 3.86s user 0.02s system 99% cpu 3.874 total % time git lg -n1 --all >/dev/null 0.83s user 0.02s system 99% cpu 0.848 total (If you need to use --all for the Linux git repo, you should not use --ignore-merge-bases). There's certainly performance improvements to be desired, but they do not appear except for very large repositories, and only when combined with --all. >> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt >> index 04ad7dd36e..cbac09028c 100644 >> --- a/Documentation/rev-list-options.txt >> +++ b/Documentation/rev-list-options.txt >> @@ -363,6 +363,14 @@ Default mode:: >> merges from the resulting history, as there are no selected >> commits contributing to this merge. >> >> +--simplify-forks:: >> + Convert the commit graph into a spanning subgraph produced by a >> + depth-first-search of the history graph, searching the leftmost >> + parent first, and discarding edges to commits already visited. >> + Useful with `--graph` to visualize repositories with many merges >> + when you are interested in was added to master, and not when the >> + branch was last rebased. > > Describing the option via the algorithm may not be the best way to > inform the user of what they will see. It also will not be informative > if the implementation changes to not perform the algorithm described > here, because that algorithm is not incremental (it is O(N) where N is > the total number of reachable commits, not ~O(n) where n is the number > of commits that will actually show up). > > An easy test is to time your command with "-n 1". While this is true, it is not the dominant effect (see above). > I'm also not crazy about "when the branch was last rebased". You > probably mean "..when you are not interested in which merge base > was used for each merge." > > Also, this does nothing without "--graph" right? Perhaps it should > enable it? Not quite. The patch interacts very nicely with gitk! > Here is a suggested alternative: > > --simplify-forks:: > Show commits that are introduced by each merge before showing > the first parent of the merge, as in `--graph`, but remove > edges from those commits to commits reachable from the first > parent. This helps to visualize repositories with many merges > when you are not interested in which merge base was used for > each merge. It also reduces the width of the graph visualization > compared to `--graph`. > > With this description, perhaps it is worth renaming the option? Perhaps > "--ignore-merge-bases"? The word "simplify" implies something like > dropping commits from history, but you are instead dropping _edges_ from > the graph. (see revision 3). >> --ancestry-path:: >> When given a range of commits to display (e.g. 'commit1..commit2' >> or 'commit2 {caret}commit1'), only display commits that exist >> diff --git a/revision.c b/revision.c >> index 5bc96444b6..51dbe21847 100644 >> --- a/revision.c >> +++ b/revision.c >> @@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg >> revs->simplify_by_decoration = 1; >> revs->limited = 1; >> revs->prune = 1; >> + } else if (!strcmp(arg, "--simplify-forks")) { >> + revs->limited = 1; >> + revs->simplify_forks = 1; > > I recommend dropping the revs->limited setting here and instead fixing the > performance instead. But maybe that should be a second patch on top of this > one. (See above.) >> } else if (!strcmp(arg, "--date-order")) { >> revs->sort_order = REV_SORT_BY_COMMIT_DATE; >> revs->topo_order = 1; >> @@ -3095,6 +3098,63 @@ static void simplify_merges(struct rev_info *revs) >> } >> } >> >> +static void simplify_forks(struct rev_info *revs) >> +{ >> + struct commit_list *stack, *list_lr, *iter_list; >> + struct commit_list **parents; > > You want "struct commit_list *parents" here for simpler use. Using a pointer to the pointer makes the amputation of the parents much more uniform: we can just pop_commit(parents), and it handles the cases of the first parent (which is addressed by commit->parents) and later parents (which are addressed by list_element->next). Of course, I'm insistent here that we should still be amputating the graph. >> + struct commit *commit, *parent; >> + >> + stack = NULL; >> + list_lr = NULL; >> + >> + clear_object_flags(SIMP_FORK_VISITED); >> + >> + for(iter_list = revs->commits; iter_list; iter_list = iter_list->next) { > > This method could use a split into at least two. I count three levels of nested > loops here, so please break them up into smaller methods. (see revision 3). >> + /* process every commit to be displayed exactly once */ >> + if(iter_list->item->object.flags & SIMP_FORK_VISITED) >> + continue; >> + clear_object_flags(SIMP_FORK_VISITING); > > This drops the flag from all commits. This will cause quadratic performance > if combined with "--all". Drop this and instead clear the flag yourself as you > visit commits. See revision 3. I now re-walk the tree as needed. Performance under --all is now extremely good (but does not stream). >> + commit_list_insert(iter_list->item, &stack); >> + iter_list->item->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING; >> + while(stack) { >> + commit = pop_commit(&stack); >> + /* process the parent nodes: removing links to >> + * commits already visited (creating a spanning tree) >> + */ >> + parents = &(commit->parents); >> + while(*parents) { > > You have some whitespace issues. Put a space between "while" and "(". Same with "if"s below. (See revision 3). I think I got them all. >> + parent = (*parents)->item; >> + if(parent->object.flags & SIMP_FORK_VISITING) { >> + /* We have already visited this commit, from the same root. >> + * We do not explore it at all. >> + */ >> + pop_commit(parents); > > I don't think you want pop_commit() here. You want to have "parents = parents->next" at the end. > > Now, if this is how you are "simplifying" the edges in the final output, then I think this is > destructive and unsafe! You are literally modifying "commit->parents" so if another operation in > Git tries to read those parents it will see the wrong data. > > Think about a different way to achieve your goal here, perhaps in the rendering portion of > graph.c instead of here. I would really like to be blissfully ignorant of branches' merge bases. I understand that this feature interacts nontrivially with things like --boundary (and in fact does retain significant information in the ordering---see the last test case in t6016). That said, it's not clear to me the use case for this when combined with other sophisticated graph manipulations. At the end of the day, I'm trying to make a feature that aids in visualizing the repository. Do you had an example case where someone would like to use this feature, but removing these parents makes these other options less useful? >> + } else if(parent->object.flags & SIMP_FORK_VISITED) { >> + /* We visited this commit before, but from a different root. >> + * Leave it attached, but do not explore it further. >> + */ >> + parents = &((*parents)->next); >> + } else { >> + /* We have not visited this commit yet. Explore it, as usual. >> + */ >> + parent->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING; >> + commit_list_insert(parent, &list_lr); >> + parents = &((*parents)->next); >> + } > > It is very unclear that your loop terminates. Instead, use > "parents = parents->next" at the end of the loop block to > make is extremely clear that the loop behaves as expected. > > Of course, this assumes that you are not being destructive > to the commit parents as you explore. (*parents) is a commit_list. If, at the start of an iteration of the loop, it has n items in it, by the end of that iteration, we will have either removed the head commit (via pop_commit) or advanced one item down the list. In either case, there are n-1 items in the list at the end of the iteration. Therefore, the loop must terminate. I've slightly adjusted the layout to make this more clear. >> + } >> + >> + /* feed the parents, right to left (reversed) onto the >> + * stack to do a depth-first traversal of the commit graph >> + */ > > nit: multi-line comment style [1] > > [1] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L285-L291 > >> + while(list_lr) { >> + commit_list_insert(pop_commit(&list_lr), &stack); >> + } > > nit: No curly braces around single-line blocks. [2] > > [2] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/Documentation/CodingGuidelines#L239-L243 Thank you (and see revision 3). >> + } >> + } >> + >> + clear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING); >> +} >> + >> static void set_children(struct rev_info *revs) >> { >> struct commit_list *l; >> @@ -3392,6 +3452,8 @@ int prepare_revision_walk(struct rev_info *revs) >> if (revs->limited) { >> if (limit_list(revs) < 0) >> return -1; >> + if (revs->simplify_forks) >> + simplify_forks(revs); >> if (revs->topo_order) >> sort_in_topological_order(&revs->commits, revs->sort_order); >> } else if (revs->topo_order) >> diff --git a/revision.h b/revision.h >> index c1af164b30..f1abdb26b0 100644 >> --- a/revision.h >> +++ b/revision.h >> @@ -51,6 +51,11 @@ >> #define TOPO_WALK_EXPLORED (1u<<27) >> #define TOPO_WALK_INDEGREE (1u<<28) >> >> +/* Re-use the TOPO_WALK flagspace for simplify_forks >> + */ >> +#define SIMP_FORK_VISITED (1u<<27) >> +#define SIMP_FORK_VISITING (1u<<28) > > I don't like that you are re-using these, as it is dangerous for later > collisions. At the moment, these flags are not used in the same code paths > because you specify "limited = 1" and that code path does not use TOPO_WALK_* > macros. I'm happy to use a different bit, and it would make me sleep easier knowing that this code is portable without worrying about this flag. I'm now using bits 23 and 24. >> #define DECORATE_SHORT_REFS 1 >> #define DECORATE_FULL_REFS 2 >> >> @@ -132,6 +137,7 @@ struct rev_info { >> no_walk:2, >> remove_empty_trees:1, >> simplify_history:1, >> + simplify_forks:1, >> show_pulls:1, >> topo_order:1, >> simplify_merges:1, >> diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh >> index f5e6e92f5b..d99214b6df 100755 >> --- a/t/t6016-rev-list-graph-simplify-history.sh >> +++ b/t/t6016-rev-list-graph-simplify-history.sh >> @@ -85,6 +85,28 @@ test_expect_success '--graph --all' ' >> test_cmp expected actual >> ' >> >> +# Make sure that simplify_histpry_forks produces a spanning tree >> +test_expect_success '--graph --simplify-forks --all' ' >> + rm -f expected && >> + echo "* $A7" >> expected && >> + echo "* $A6" >> expected && >> + echo "|\ " >> expected && >> + echo "| * $C4" >> expected && >> + echo "| * $C3" >> expected && >> + echo "* $A5" >> expected && >> + echo "*-. $A4" >> expected && >> + echo "|\ \ " >> expected && >> + echo "| | * $C2" >> expected && >> + echo "| | * $C1" >> expected && >> + echo "| * $B2" >> expected && >> + echo "| * $B1" >> expected && >> + echo "* $A3" >> expected && >> + echo "* $A2" >> expected && >> + echo "* $A1" >> expected && > > Do not use too many echos like this. Instead use t4215-log-skewed-merges.sh > as an example [3]. > > [3] https://github.com/git/git/blob/86ab15cb154862b6fa5cc646dac27532f881e1fb/t/t4215-log-skewed-merges.sh#L24-L37 > > I also hope that you can find more complicated cases to > test, including: > > 1. A merge that brings in a merge (think a feature branch) > 2. A merge that brings in a twisted merge (think a user using "git pull"). > > Here are some example --graph and --simplify-forks outputs to try. I > have not tested these myself, but I believe they are interesting test > cases that can trip up other algorithms. > > Merge bringing a merge (non-twisted): > > --graph --simplify-forks > * * > |\ |\ > | * | * > | |\ | |\ > | | * | | * > | * | | * > * | | * > |/ / * > * / * > |/ > * > > Twisted merge: > > --graph --simplify-forks > * * > |\ |\ > | * | * > | |\ | * > | * | * > | | | * > * |/ * > |/| > * | > |/ > * That is much nicer. I've cleaned up t6106 in a similar way, and test --ignore-merge-bases there, t4215, and in the new t4216. Thanks, Antonio
On 5/1/2020 10:13 AM, Antonio Russo wrote: > On 4/29/20 7:12 AM, Derrick Stolee wrote: >> On 4/29/2020 4:01 AM, Antonio Russo wrote: >>> When used with --graph, instead of displaying the full graph, display a >>> spanning subgraph produced by a depth-first search of the graph visiting >>> parents from left to right. Edges to already visited commits are >>> discarded. This process is repeated for every commit to be displayed. >>> >>> This is valuable to reduce visual clutter when there are many merges >>> that were not rebased onto each other and the user is primarily >>> interested in the state of the branch being merged into. >> >> My earlier comment to recommend how to fix the test failures intended >> to demonstrate that this area of code requires a bit of precision. I >> took some time to review this patch, but I find it needs some significant >> updates. >> >> tl;dr: The way you manipulate the commit parents seems incorrect to me, >> but perhaps there is enough prior art in the way we simplify parents to >> make that acceptable. Someone else will need to chime in on that part. > > First, thank you for taking the time look at this. I understand your > hesitation about the "amputation" of the history, but in some sense > that's the point of this option. I really want to be ignorant of the > details of when the fork branched off. I would like the reported > history to be appear nearly equivalent to a rebase-and-fastforward only > merge style, which results in a much simpler git log --graph. > >> It may be possible to do this "drop edges" entirely inside of graph.c >> (the graph rendering code) instead of revision.c, which would automatically >> work with the performance gains from the newer topo-walk algorithm. > > Non-local information about the commit graph needs to be used to do this > amputation of the history. We cannot know how many parents we want to > display until we've completely explored all the parents of that node. > Unfortunately, that means that the whole graph needs to be loaded, and I > cannot really see how there would be any gain by doing this in graph.c. > > Caveat: there are semi-streaming DFS implementations (i.e., O(n log n) > space) that we might be able to use to get the first line out the door > quicker. I would, however, like to leave that to another patch. > > I will also add that, for the tests I've done, all performance penalties > have been insignificant (less than ~5% for showing the first commit), > while there are significant performance _improvements_, e.g., ~40% for > displaying the full tree. > > A notable exception is --all, which can be ~50x faster for the full > output, but is often dramatically slower to show anything (i.e., the > first line). > >> There are enough deviations from code and test style that this will >> need a significant revision regardless. > > (Please see forthcoming revision 3). > >>> This second revision of the patch sets revs->limited. This forces the >>> graph of commits to be loaded, and simplfiy_forks() therefore reliably >>> traverses it. This addresses the test failures mentioned before (see [1]). >> >> This will have a significant performance impact on the option, as you will >> not see even the first result until the DFS has completed. > > First of all, short of using some other, more sophisticated streaming > version of this algorithm, the full DFS must finish before the first > commit having two (or more) parents can be shown. > > That said, the performance is not significantly affected: > > I ran the following test (2.26.2, with my patch on top of it): > (git lg = git log --graph --pretty=oneline) > > % time git lg -n1 --ignore-merge-bases e896a286df > /dev/null > 0.73s user 0.02s system 99% cpu 0.746 total > > % time git lg -n1 e896a286df > /dev/null > 0.72s user 0.01s system 99% cpu 0.731 total > > For the linux git repo: > > % time git lg -n1 --ignore-merge-bases v5.7-rc3 >/dev/null > 9.25s user 0.39s system 99% cpu 9.646 total > > % time git lg -n1 v5.7-rc3 >/dev/null > 9.02s user 0.35s system 99% cpu 9.378 total > > So the performance seems basically unaffected for very limited graphs. > It's also about 40% faster for complicated ones (as mentioned in my > first email): > > % time git lg --ignore-merge-bases e870325ee8 > /dev/null > 0.83s user 0.06s system 99% cpu 0.886 total > > % time git lg e870325ee8 > /dev/null > 1.41s user 0.03s system 99% cpu 1.443 total > > For the linux git repo: > > % time git lg --ignore-merge-bases v5.7-rc3 >/dev/null > 11.86s user 0.62s system 99% cpu 12.489 total > > % time git lg v5.7-rc3 >/dev/null > 21.56s user 0.55s system 99% cpu 22.108 total First, run `git commit-graph write --reachable` to create a commit-graph file which has generation numbers. In this case, I get the following: $ time git log --oneline --graph v5.7-rc3 >/dev/null real 0m13.548s user 0m13.348s sys 0m0.200s $ time git log --oneline --graph -n 1 v5.7-rc3 >/dev/null real 0m0.007s user 0m0.004s sys 0m0.004s Notice exactly how much better this gets for the first result with that file. > This is because the amputated graph is much simpler, and the rest of the > code needs to do much less work. > > Passing --all is another beast, and does indeed suffer: > > % time git lg --ignore-merge-bases --all >/dev/null > 4.06s user 0.04s system 99% cpu 4.105 total > > % time git lg --all >/dev/null > 189.59s user 0.04s system 99% cpu 3:09.65 total > > (and for the first line) > > % time git lg -n1 --ignore-merge-bases --all >/dev/null > 3.86s user 0.02s system 99% cpu 3.874 total > > % time git lg -n1 --all >/dev/null > 0.83s user 0.02s system 99% cpu 0.848 total > > (If you need to use --all for the Linux git repo, you should not use > --ignore-merge-bases). I think this is a deficiency in your implementation, not a hard rule about how these options would need to interact. Thanks, -Stolee
diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt index 04ad7dd36e..cbac09028c 100644 --- a/Documentation/rev-list-options.txt +++ b/Documentation/rev-list-options.txt @@ -363,6 +363,14 @@ Default mode:: merges from the resulting history, as there are no selected commits contributing to this merge. +--simplify-forks:: + Convert the commit graph into a spanning subgraph produced by a + depth-first-search of the history graph, searching the leftmost + parent first, and discarding edges to commits already visited. + Useful with `--graph` to visualize repositories with many merges + when you are interested in was added to master, and not when the + branch was last rebased. + --ancestry-path:: When given a range of commits to display (e.g. 'commit1..commit2' or 'commit2 {caret}commit1'), only display commits that exist diff --git a/revision.c b/revision.c index 5bc96444b6..51dbe21847 100644 --- a/revision.c +++ b/revision.c @@ -2082,6 +2082,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg revs->simplify_by_decoration = 1; revs->limited = 1; revs->prune = 1; + } else if (!strcmp(arg, "--simplify-forks")) { + revs->limited = 1; + revs->simplify_forks = 1; } else if (!strcmp(arg, "--date-order")) { revs->sort_order = REV_SORT_BY_COMMIT_DATE; revs->topo_order = 1; @@ -3095,6 +3098,63 @@ static void simplify_merges(struct rev_info *revs) } } +static void simplify_forks(struct rev_info *revs) +{ + struct commit_list *stack, *list_lr, *iter_list; + struct commit_list **parents; + struct commit *commit, *parent; + + stack = NULL; + list_lr = NULL; + + clear_object_flags(SIMP_FORK_VISITED); + + for(iter_list = revs->commits; iter_list; iter_list = iter_list->next) { + /* process every commit to be displayed exactly once */ + if(iter_list->item->object.flags & SIMP_FORK_VISITED) + continue; + clear_object_flags(SIMP_FORK_VISITING); + commit_list_insert(iter_list->item, &stack); + iter_list->item->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING; + while(stack) { + commit = pop_commit(&stack); + /* process the parent nodes: removing links to + * commits already visited (creating a spanning tree) + */ + parents = &(commit->parents); + while(*parents) { + parent = (*parents)->item; + if(parent->object.flags & SIMP_FORK_VISITING) { + /* We have already visited this commit, from the same root. + * We do not explore it at all. + */ + pop_commit(parents); + } else if(parent->object.flags & SIMP_FORK_VISITED) { + /* We visited this commit before, but from a different root. + * Leave it attached, but do not explore it further. + */ + parents = &((*parents)->next); + } else { + /* We have not visited this commit yet. Explore it, as usual. + */ + parent->object.flags |= SIMP_FORK_VISITED | SIMP_FORK_VISITING; + commit_list_insert(parent, &list_lr); + parents = &((*parents)->next); + } + } + + /* feed the parents, right to left (reversed) onto the + * stack to do a depth-first traversal of the commit graph + */ + while(list_lr) { + commit_list_insert(pop_commit(&list_lr), &stack); + } + } + } + + clear_object_flags(SIMP_FORK_VISITED | SIMP_FORK_VISITING); +} + static void set_children(struct rev_info *revs) { struct commit_list *l; @@ -3392,6 +3452,8 @@ int prepare_revision_walk(struct rev_info *revs) if (revs->limited) { if (limit_list(revs) < 0) return -1; + if (revs->simplify_forks) + simplify_forks(revs); if (revs->topo_order) sort_in_topological_order(&revs->commits, revs->sort_order); } else if (revs->topo_order) diff --git a/revision.h b/revision.h index c1af164b30..f1abdb26b0 100644 --- a/revision.h +++ b/revision.h @@ -51,6 +51,11 @@ #define TOPO_WALK_EXPLORED (1u<<27) #define TOPO_WALK_INDEGREE (1u<<28) +/* Re-use the TOPO_WALK flagspace for simplify_forks + */ +#define SIMP_FORK_VISITED (1u<<27) +#define SIMP_FORK_VISITING (1u<<28) + #define DECORATE_SHORT_REFS 1 #define DECORATE_FULL_REFS 2 @@ -132,6 +137,7 @@ struct rev_info { no_walk:2, remove_empty_trees:1, simplify_history:1, + simplify_forks:1, show_pulls:1, topo_order:1, simplify_merges:1, diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh index f5e6e92f5b..d99214b6df 100755 --- a/t/t6016-rev-list-graph-simplify-history.sh +++ b/t/t6016-rev-list-graph-simplify-history.sh @@ -85,6 +85,28 @@ test_expect_success '--graph --all' ' test_cmp expected actual ' +# Make sure that simplify_histpry_forks produces a spanning tree +test_expect_success '--graph --simplify-forks --all' ' + rm -f expected && + echo "* $A7" >> expected && + echo "* $A6" >> expected && + echo "|\ " >> expected && + echo "| * $C4" >> expected && + echo "| * $C3" >> expected && + echo "* $A5" >> expected && + echo "*-. $A4" >> expected && + echo "|\ \ " >> expected && + echo "| | * $C2" >> expected && + echo "| | * $C1" >> expected && + echo "| * $B2" >> expected && + echo "| * $B1" >> expected && + echo "* $A3" >> expected && + echo "* $A2" >> expected && + echo "* $A1" >> expected && + git rev-list --graph --simplify-forks --all > actual && + test_cmp expected actual + ' + # Make sure the graph_is_interesting() code still realizes # that undecorated merges are interesting, even with --simplify-by-decoration test_expect_success '--graph --simplify-by-decoration' ' @@ -157,6 +179,20 @@ test_expect_success '--graph --full-history -- bar.txt' ' test_cmp expected actual ' +test_expect_success '--graph --simplify-forks --full-history -- bar.txt' ' + rm -f expected && + echo "* $A7" >> expected && + echo "* $A6" >> expected && + echo "|\\ " >> expected && + echo "| * $C4" >> expected && + echo "* $A5" >> expected && + echo "* $A4" >> expected && + echo "* $A3" >> expected && + echo "* $A2" >> expected && + git rev-list --graph --simplify-forks --full-history --all -- bar.txt > actual && + test_cmp expected actual + ' + test_expect_success '--graph --full-history --simplify-merges -- bar.txt' ' rm -f expected && echo "* $A7" >> expected && @@ -172,6 +208,20 @@ test_expect_success '--graph --full-history --simplify-merges -- bar.txt' ' test_cmp expected actual ' +test_expect_success '--graph --simplify-forks --full-history --simplify-merges -- bar.txt' ' + rm -f expected && + echo "* $A7" >> expected && + echo "* $A6" >> expected && + echo "|\\ " >> expected && + echo "| * $C4" >> expected && + echo "* $A5" >> expected && + echo "* $A3" >> expected && + echo "* $A2" >> expected && + git rev-list --graph --simplify-forks --full-history --simplify-merges --all \ + -- bar.txt > actual && + test_cmp expected actual + ' + test_expect_success '--graph -- bar.txt' ' rm -f expected && echo "* $A7" >> expected &&
When used with --graph, instead of displaying the full graph, display a spanning subgraph produced by a depth-first search of the graph visiting parents from left to right. Edges to already visited commits are discarded. This process is repeated for every commit to be displayed. This is valuable to reduce visual clutter when there are many merges that were not rebased onto each other and the user is primarily interested in the state of the branch being merged into. Also adds documentation and tests of the above. Signed-off-by: Antonio Russo <antonio.e.russo@gmail.com> --- Documentation/rev-list-options.txt | 8 +++ revision.c | 62 ++++++++++++++++++++++ revision.h | 6 +++ t/t6016-rev-list-graph-simplify-history.sh | 50 +++++++++++++++++ 4 files changed, 126 insertions(+) Hello, This second revision of the patch sets revs->limited. This forces the graph of commits to be loaded, and simplfiy_forks() therefore reliably traverses it. This addresses the test failures mentioned before (see [1]). Antonio [1] https://travis-ci.org/github/aerusso/git/builds/680894920