commit 83e5e9a11730a93d948aabbafdb2592713eb6f28 from: Stefan Sperling date: Wed Mar 27 10:49:09 2024 UTC add log -t option which enables topological sorting of commits Because the current implementation of toposort is expensive, add a flag which enables it. I would rather not have this option and just use toposort by default, however more work is required to achieve acceptable performance. ok op@ commit - 2afa256de5f9027b941e0a912d57fa5201a6cfc6 commit + 83e5e9a11730a93d948aabbafdb2592713eb6f28 blob - 0b7ff7916ba48b09d48cbc1c37cf75175316b469 blob + ee41732e49ededaf4c54218c0d0b9deb2c1feff9 --- got/got.1 +++ got/got.1 @@ -890,7 +890,7 @@ and gives no special significance to the location of p in a pattern. .It Xo .Cm log -.Op Fl bdPpRs +.Op Fl bdPpRst .Op Fl C Ar number .Op Fl c Ar commit .Op Fl l Ar N @@ -1038,6 +1038,13 @@ Cannot be used together with the or .Fl P option. +.It Fl t +Display commits in topological order. +This option has no effect without the +.Fl b +option because a linear history is sorted in topological order by definition. +Topological sorting is disabled by default because the present implementation +requires that commit history is fully traversed before any output can be shown. .It Fl x Ar commit Stop traversing commit history immediately after the specified .Ar commit blob - 1a1732a2994a8428496e498b70ebb81e222507aa blob + 74e2fb65d552093211aa85ccb3eaaa5d77f81f6f --- got/got.c +++ got/got.c @@ -4459,7 +4459,7 @@ print_commits(struct got_object_id *root_id, struct go struct got_repository *repo, const char *path, int show_changed_paths, int show_diffstat, int show_patch, const char *search_pattern, int diff_context, int limit, int log_branches, int reverse_display_order, - struct got_reflist_object_id_map *refs_idmap, int one_line, + struct got_reflist_object_id_map *refs_idmap, int one_line, int toposort, FILE *tmpfile) { const struct got_error *err; @@ -4481,8 +4481,13 @@ print_commits(struct got_object_id *root_id, struct go err = got_commit_graph_open(&graph, path, !log_branches); if (err) return err; - err = got_commit_graph_iter_start(graph, root_id, repo, - check_cancelled, NULL); + if (log_branches && toposort) { + err = got_commit_graph_toposort(graph, root_id, repo, + check_cancelled, NULL); + } else { + err = got_commit_graph_iter_start(graph, root_id, repo, + check_cancelled, NULL); + } if (err) goto done; for (;;) { @@ -4610,7 +4615,7 @@ done: __dead static void usage_log(void) { - fprintf(stderr, "usage: %s log [-bdPpRs] [-C number] [-c commit] " + fprintf(stderr, "usage: %s log [-bdPpRst] [-C number] [-c commit] " "[-l N] [-r repository-path] [-S search-pattern] [-x commit] " "[path]\n", getprogname()); exit(1); @@ -4646,6 +4651,7 @@ cmd_log(int argc, char *argv[]) int diff_context = -1, ch; int show_changed_paths = 0, show_patch = 0, limit = 0, log_branches = 0; int show_diffstat = 0, reverse_display_order = 0, one_line = 0; + int toposort = 0; const char *errstr; struct got_reflist_head refs; struct got_reflist_object_id_map *refs_idmap = NULL; @@ -4663,7 +4669,7 @@ cmd_log(int argc, char *argv[]) limit = get_default_log_limit(); - while ((ch = getopt(argc, argv, "bC:c:dl:PpRr:S:sx:")) != -1) { + while ((ch = getopt(argc, argv, "bC:c:dl:PpRr:S:stx:")) != -1) { switch (ch) { case 'b': log_branches = 1; @@ -4709,6 +4715,9 @@ cmd_log(int argc, char *argv[]) case 's': one_line = 1; break; + case 't': + toposort = 1; + break; case 'x': end_commit = optarg; break; @@ -4875,7 +4884,7 @@ cmd_log(int argc, char *argv[]) error = print_commits(start_id, end_id, repo, path ? path : "", show_changed_paths, show_diffstat, show_patch, search_pattern, diff_context, limit, log_branches, reverse_display_order, - refs_idmap, one_line, tmpfile); + refs_idmap, one_line, toposort, tmpfile); done: free(path); free(repo_path); blob - 4a83ec7819b07c9e4a689fc50177a7b979abbbf9 blob + c3e22d2178b4eebd38723079274f19c9e8b9d2d5 --- regress/cmdline/log.sh +++ regress/cmdline/log.sh @@ -1241,6 +1241,68 @@ test_log_commit_keywords() { test_done "$testroot" "$ret" } +test_log_toposort() { + local testroot=`test_init log_toposort` + local commit0=`git_show_head $testroot/repo` + local author_time0=`git_show_author_time $testroot/repo` + + got checkout $testroot/repo $testroot/wt > /dev/null + ret=$? + if [ $ret -ne 0 ]; then + test_done "$testroot" "$ret" + return 1 + fi + + echo aaa > $testroot/wt/alpha + (cd $testroot/wt && got commit -m 'change alpha' >/dev/null) + local commit1=`git_show_head $testroot/repo` + local author_time1=`git_show_author_time $testroot/repo` + + got branch -r $testroot/repo -c $commit0 newbranch + (cd $testroot/wt && got update -b newbranch > /dev/null) + echo ddd > $testroot/wt/gamma/delta + (cd $testroot/wt && got commit -m 'change delta' >/dev/null) + local commit2=`git_show_branch_head $testroot/repo newbranch` + local author_time2=`git_show_author_time $testroot/repo newbranch` + + echo zzz > $testroot/wt/epsilon/zeta + (cd $testroot/wt && got commit -m 'change zeta' >/dev/null) + local commit3=`git_show_head $testroot/repo` + local author_time3=`git_show_author_time $testroot/repo newbranch` + + (cd $testroot/wt && got update -b master > /dev/null) + (cd $testroot/wt && got merge newbranch > /dev/null) + local merge_commit=`git_show_head $testroot/repo` + local merge_time=`git_show_author_time $testroot/repo` + + local short_commit0=`trim_obj_id 33 $commit0` + local short_commit1=`trim_obj_id 33 $commit1` + local short_commit2=`trim_obj_id 33 $commit2` + local short_commit3=`trim_obj_id 33 $commit3` + + d_0=`date -u -r $author_time0 +"%G-%m-%d"` + d_1=`date -u -r $author_time1 +"%G-%m-%d"` + d_2=`date -u -r $author_time2 +"%G-%m-%d"` + d_3=`date -u -r $author_time3 +"%G-%m-%d"` + d_m=`date -u -r $merge_time +"%G-%m-%d"` + + got log -r $testroot/repo -s -b -t > $testroot/stdout + cat > $testroot/stdout.expected <