{"thread":{"id":"52579","subject":"[PATCH 0/1] Preserve topological ordering after merges","startedAt":"2020-01-07T10:31:02Z","lastAt":"2020-01-08T17:04:50Z","messageCount":11,"participants":["Sergey Rudyshin via GitGitGadget","Johannes Schindelin","Derrick Stolee","Junio C Hamano","Sergey Rudyshin"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"389346","messageId":"pull.514.git.1578393057.gitgitgadget@gmail.com","threadId":"52579","inReplyTo":null,"subject":"[PATCH 0/1] Preserve topological ordering after merges","fromName":"Sergey Rudyshin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-01-07T10:30:56Z","receivedAt":"2020-01-07T10:31:02Z","isPatch":true,"sender":{"key":"540555@gmail.com","avatar":null},"body":"This modifies the algoritm of topopological ordering. The problem with the\ncurrent algoritm is that it displays the graph below as following\n\n* E\n|\\\n| * D\n| |\\\n| |/\n|/|\n* | C\n| * B\n|/\n* A\n\ncommit B is placed between A and C, which is wrong because E stays that D\nand B comes after C\n\nthe only correct solution here is\n\n* E\n|\\\n| * D\n| |\\\n| |/\n|/|\n| * B\n* | C\n|/\n* A\n\nwhile it seems that it contradicts to D staiting that C shoud be between D\nand B The new algorithm solves this issue\n\nHere is an example: walk to to the root via \"first\" parents go E -> C -> A\nprint A because it has no parents step back to C print C because it has no\nother parents then step back to E go D -> B -> A do not print A becase A is\nalready printed step back to B print B so on\n\nThis change makes option \"--topo-order\" obsolete, because for a single\ncommit there is only one way to order parents. \"--date-order\" and\n\"--author-date-order\" are preserved and make sence only for the case when\nmultiple commits are given to be able to sort those commits.\n\nSergey Rudyshin (1):\n Preserve topological ordering after merges This modifies the algorithm\n of topopological ordering. The problem with the current algoritm is\n that it displays the graph below as follows\n\n Documentation/git-rev-list.txt | 4 +-\n Documentation/rev-list-options.txt | 41 +++---\n commit.c | 149 ++++++++++++++-------\n commit.h | 4 +-\n t/t4202-log.sh | 15 +--\n t/t4215-log-skewed-merges.sh | 44 +++---\n t/t6003-rev-list-topo-order.sh | 54 ++++----\n t/t6012-rev-list-simplify.sh | 8 +-\n t/t6016-rev-list-graph-simplify-history.sh | 41 +++---\n t/t6600-test-reach.sh | 6 +-\n 10 files changed, 214 insertions(+), 152 deletions(-)\n\n\nbase-commit: 8679ef24ed64018bb62170c43ce73e0261c0600a\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-514%2FSergeyRudyshin%2Ftopo_order_fix-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-514/SergeyRudyshin/topo_order_fix-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/514\n-- \ngitgitgadget\n"},{"id":"389347","messageId":"542a02020c8578d0e004cb9c929bced8719b902a.1578393057.git.gitgitgadget@gmail.com","threadId":"52579","inReplyTo":"pull.514.git.1578393057.gitgitgadget@gmail.com","subject":"[PATCH 1/1] Preserve topological ordering after merges This modifies the algorithm of topopological ordering. The problem with the current algoritm is that it displays the graph below as follows","fromName":"Sergey Rudyshin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-01-07T10:30:57Z","receivedAt":"2020-01-07T10:31:04Z","isPatch":true,"sender":{"key":"540555@gmail.com","avatar":null},"body":"From: Sergey Rudyshin <540555@gmail.com>\n\n* E\n|\\\n| * D\n| |\\\n| |/\n|/|\n* | C\n| * B\n|/\n* A\n\ncommit B is placed between A and C, which is wrong\nbecause E stays that D and B comes after C\n\nthe only correct solution here is\n\n* E\n|\\\n| * D\n| |\\\n| |/\n|/|\n| * B\n* | C\n|/\n* A\n\nwhile it seems that it contradicts to\nD stating that C should be between D and B\nThe new algorithm solves this issue\n\nHere is an example:\n* walk to to the root via \"first\" parents;\n* go E -> C -> A;\n* print A because it has no parents;\n* step back to C;\n* print C because it has no other parents;\n* then step back to E;\n* go D -> B -> A;\n* do not print A because A is already printed;\n* step back to B;\n* print B;\n* so on.\n\nThis change makes option \"--topo-order\" obsolete, because\nthere is only one way to order parents of a single commit.\n\"--date-order\" and \"--author-date-order\" are preserved and make sense\nonly for the case when multiple commits are given\nto be able to sort those commits.\n\nSigned-off-by: Sergey Rudyshin <540555@gmail.com>\n---\n Documentation/git-rev-list.txt | 4 +-\n Documentation/rev-list-options.txt | 41 +++---\n commit.c | 149 ++++++++++++++-------\n commit.h | 4 +-\n t/t4202-log.sh | 15 +--\n t/t4215-log-skewed-merges.sh | 44 +++---\n t/t6003-rev-list-topo-order.sh | 54 ++++----\n t/t6012-rev-list-simplify.sh | 8 +-\n t/t6016-rev-list-graph-simplify-history.sh | 41 +++---\n t/t6600-test-reach.sh | 6 +-\n 10 files changed, 214 insertions(+), 152 deletions(-)\n\ndiff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt\nindex 025c911436..ad1fda7a54 100644\n--- a/Documentation/git-rev-list.txt\n+++ b/Documentation/git-rev-list.txt\n@@ -3,7 +3,7 @@ git-rev-list(1)\n \n NAME\n ----\n-git-rev-list - Lists commit objects in reverse chronological order\n+git-rev-list - Lists commit objects in reverse topological order\n \n \n SYNOPSIS\n@@ -17,7 +17,7 @@ DESCRIPTION\n List commits that are reachable by following the `parent` links from the\n given commit(s), but exclude commits that are reachable from the one(s)\n given with a '{caret}' in front of them. The output is given in reverse\n-chronological order by default.\n+topological order by default.\n \n You can think of this as a set operation. Commits given on the command\n line form a set of commits that are reachable from any of them, and then\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex bfd02ade99..7ab2f451ae 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -643,39 +643,42 @@ ifndef::git-shortlog[]\n Commit Ordering\n ~~~~~~~~~~~~~~~\n \n-By default, the commits are shown in reverse chronological order.\n+By default, the commits are shown in reverse topological order.\n++\n+Meaning that no parents are shown before all of its children and\n+merges do not change the previous order.\n++\n+E.g., if commit M0 produces topologically ordered list of \n+commits L0 then commit M1 created by merging any commit into M0\n+produces list L1 which starts with L0\n++\n+In case if multiple commits are given via the command line\n+the following parameters determine the order among them:\n \n --date-order::\n-\tShow no parents before all of its children are shown, but\n-\totherwise show commits in the commit timestamp order.\n+\tshow commits in the commit timestamp order.\n \n --author-date-order::\n-\tShow no parents before all of its children are shown, but\n-\totherwise show commits in the author timestamp order.\n+\tshow commits in the author timestamp order.\n \n --topo-order::\n-\tShow no parents before all of its children are shown, and\n-\tavoid showing commits on multiple lines of history\n-\tintermixed.\n+\tshow commits in the commit timestamp order.\n+\tthis is deprecated and will be\n+\tremoved in the future.\n +\n For example, in a commit history like this:\n +\n ----------------------------------------------------------------\n-\n- ---1----2----4----7\n-\t\\\t \\\n-\t 3----5----6----8---\n-\n+ 1----2-----------5\n+ \\ \\ /\n+ -----\\---3---4---6\n+ \\ /\n+ ----\n ----------------------------------------------------------------\n +\n where the numbers denote the order of commit timestamps, `git\n rev-list` and friends with `--date-order` show the commits in the\n-timestamp order: 8 7 6 5 4 3 2 1.\n-+\n-With `--topo-order`, they would show 8 6 5 3 7 4 2 1 (or 8 7 4 2 6 5\n-3 1); some older commits are shown before newer ones in order to\n-avoid showing the commits from two parallel development track mixed\n-together.\n+following order: 1 2 3 4 5 6.\n \n --reverse::\n \tOutput the commits chosen to be shown (see Commit Limiting\ndiff --git a/commit.c b/commit.c\nindex 434ec030d6..01e9d07db9 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -738,6 +738,12 @@ int compare_commits_by_author_date(const void *a_, const void *b_,\n \treturn 0;\n }\n \n+static int compare_commits_by_author_date_rev(const void *a_, const void *b_,\n+\t\t\t\t void *cb_data)\n+{\n+\treturn compare_commits_by_author_date(b_, a_, cb_data);\n+}\n+\n int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)\n {\n \tconst struct commit *a = a_, *b = b_;\n@@ -767,36 +773,83 @@ int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n \treturn 0;\n }\n \n+static int compare_commits_by_commit_date_rev(const void *a_, const void *b_, void *unused)\n+{\n+\treturn compare_commits_by_commit_date (b_, a_, unused);\n+}\n+\n+struct maze {\n+\tstruct commit *ret;\n+\tstruct commit *out;\n+};\n+\n+define_commit_slab(maze_slab, struct maze *);\n+\n+/*\n+ * returns the next commit while exploring the maze\n+ * current commit has the information:\n+ * \t- what was the last commit we went for (OUT)\n+ * \t- from which commit we came in (RET)\n+ * trying to find a parent next to OUT\n+ * if it does not exists returns RET\n+ * otherwise returns the found parent\n+ */\n+static struct commit *get_next(struct commit *commit, struct maze *mz, struct indegree_slab *indegree)\n+{\n+\tstruct commit_list *parents = commit->parents;\n+\tstruct commit *next = NULL;\n+\tint found = 0;\n+\n+\twhile (parents) {\n+\t\tstruct commit *parent = parents->item;\n+\n+\t\tif (*indegree_slab_at(indegree, parent)) {\n+\n+\t\t\tif (!mz->out || found) {\n+\t\t\t\tnext = parent;\n+\t\t\t\tbreak;\n+\t\t\t} else if (mz->out == parent) {\n+\t\t\t\tfound = 1;\n+\t\t\t}\n+\t\t}\n+\t\tparents = parents->next;\n+\t}\n+\n+\tif (!next) next = mz->ret;\n+\n+\treturn next;\n+}\n+\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 {\n \tstruct commit_list *next, *orig = *list;\n-\tstruct commit_list **pptr;\n+\tstruct commit_list **pptr = list;\n \tstruct indegree_slab indegree;\n-\tstruct prio_queue queue;\n+\tstruct prio_queue queue_tips;\n \tstruct commit *commit;\n \tstruct author_date_slab author_date;\n+\tstruct maze_slab maze;\n+\tstruct maze *mz;\n \n \tif (!orig)\n \t\treturn;\n \t*list = NULL;\n \n \tinit_indegree_slab(&indegree);\n-\tmemset(&queue, '\\0', sizeof(queue));\n+\tinit_maze_slab(&maze);\n+\tmemset(&queue_tips, '\\0', sizeof(queue_tips));\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+\tdefault: \n+\t\tqueue_tips.compare = compare_commits_by_commit_date_rev;\n \t\tbreak;\n \tcase 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\tqueue_tips.compare = compare_commits_by_author_date_rev;\n+\t\tqueue_tips.cb_data = &author_date;\n \t\tbreak;\n \t}\n \n@@ -804,9 +857,10 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n \t\t*(indegree_slab_at(&indegree, commit)) = 1;\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\tmz = xmalloc(sizeof(struct maze));\n+\t\tmz->ret = NULL;\n+\t\tmz->out = NULL;\n+\t\t*(maze_slab_at(&maze, commit)) = mz;\n \t}\n \n \t/* update the indegree */\n@@ -832,51 +886,56 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n \n-\t\tif (*(indegree_slab_at(&indegree, commit)) == 1)\n-\t\t\tprio_queue_put(&queue, commit);\n+\t\tif (*(indegree_slab_at(&indegree, commit)) == 1) {\n+\t\t\t/* also record the author dates, if needed */\n+\t\t\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n+\t\t\t\trecord_author_date(&author_date, commit);\n+\t\t\tprio_queue_put(&queue_tips, commit);\n+\t\t}\n \t}\n \n-\t/*\n-\t * This is unfortunate; the initial tips need to be shown\n-\t * in the order given from the revision traversal machinery.\n-\t */\n-\tif (sort_order == REV_SORT_IN_GRAPH_ORDER)\n-\t\tprio_queue_reverse(&queue);\n-\n \t/* We no longer need the commit list */\n \tfree_commit_list(orig);\n \n \tpptr = list;\n \t*list = NULL;\n-\twhile ((commit = prio_queue_get(&queue)) != NULL) {\n-\t\tstruct commit_list *parents;\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 \n-\t\t\tif (!*pi)\n+\twhile ((commit = prio_queue_get(&queue_tips)) != NULL) {\n+\t\tstruct commit *prev_commit = NULL;\n+\t\twhile (commit) {\n+\t\t\tmz = *(maze_slab_at(&maze, commit));\n+\t\t\tif (!prev_commit) {\n+\t\t\t\t/* either a new tip or \n+\t\t\t\t * after entering an already visited commit\n+\t\t\t\t */\n+\t\t\t}\n+\t\t\telse if (!mz->out) {\n+\t\t\t\t/* happens only once for every commit\n+\t\t\t\t * note that for tips RET is set to NULL\n+\t\t\t\t */\n+\t\t\t\tmz->ret = prev_commit;\n+\t\t\t} \n+\t\t\telse if (prev_commit != mz->out) {\n+\t\t\t\t/* entered an already visited commit\n+\t\t\t\t * step back\n+\t\t\t\t */\n+\t\t\t\tcommit = prev_commit;\n+\t\t\t\tprev_commit = NULL;\n \t\t\t\tcontinue;\n-\n-\t\t\t/*\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\tif (--(*pi) == 1)\n-\t\t\t\tprio_queue_put(&queue, parent);\n+\t\t\t}\n+\t\t\tmz->out = get_next(commit, mz, &indegree);\n+\t\t\tif (mz->out == mz->ret) {\n+\t\t\t\t/* upon leaving a commit emit it */\n+\t\t\t\t*pptr = commit_list_insert(commit, pptr);\n+\t\t\t}\n+\t\t\tprev_commit = commit;\n+\t\t\tcommit = mz->out;\n \t\t}\n-\t\t/*\n-\t\t * all children of commit have already been\n-\t\t * emitted. we can emit it now.\n-\t\t */\n-\t\t*(indegree_slab_at(&indegree, commit)) = 0;\n-\n-\t\tpptr = &commit_list_insert(commit, pptr)->next;\n \t}\n \n \tclear_indegree_slab(&indegree);\n-\tclear_prio_queue(&queue);\n+\tclear_maze_slab(&maze);\n+\tclear_prio_queue(&queue_tips);\n \tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n \t\tclear_author_date_slab(&author_date);\n }\ndiff --git a/commit.h b/commit.h\nindex 221cdaa34b..1fe3cc240e 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -209,7 +209,7 @@ struct commit *pop_commit(struct commit_list **stack);\n void clear_commit_marks(struct commit *commit, unsigned int mark);\n void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark);\n \n-\n+/* TODO get rid of rev_sort_order in a favour of positional parameters */\n enum rev_sort_order {\n \tREV_SORT_IN_GRAPH_ORDER = 0,\n \tREV_SORT_BY_COMMIT_DATE,\n@@ -222,8 +222,6 @@ enum rev_sort_order {\n * invariant of resulting list is:\n * a reachable from b => ord(b) < ord(a)\n * sort_order further specifies:\n- * REV_SORT_IN_GRAPH_ORDER: try to show a commit on a single-parent\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);\ndiff --git a/t/t4202-log.sh b/t/t4202-log.sh\nindex 2c9489484a..46f04b36a3 100755\n--- a/t/t4202-log.sh\n+++ b/t/t4202-log.sh\n@@ -635,17 +635,16 @@ test_expect_success 'set up more tangled history' '\n cat > expect <<\\EOF\n * Merge tag 'reach'\n |\\\n-| \\\n+| * reach\n+| |\n | \\\n *-. \\ Merge tags 'octopus-a' and 'octopus-b'\n |\\ \\ \\\n-* | | | seventh\n | | * | octopus-b\n-| |/ /\n-|/| |\n-| * | octopus-a\n-|/ /\n-| * reach\n+| | |/\n+| * / octopus-a\n+| |/\n+* / seventh\n |/\n * Merge branch 'tangle'\n |\\\n@@ -673,7 +672,7 @@ cat > expect <<\\EOF\n * initial\n EOF\n \n-test_expect_success 'log --graph with merge' '\n+test_expect_success 'log --graph with merge tag reach' '\n \tgit log --graph --date-order --pretty=tformat:%s |\n \t\tsed \"s/ *\\$//\" >actual &&\n \ttest_cmp expect actual\ndiff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh\nindex 18709a723e..91630c0cae 100755\n--- a/t/t4215-log-skewed-merges.sh\n+++ b/t/t4215-log-skewed-merges.sh\n@@ -5,7 +5,7 @@ test_description='git log --graph of skewed merges'\n . ./test-lib.sh\n \n check_graph () {\n-\tcat >expect &&\n+\tsed \"s/ *$//\" >expect &&\n \tgit log --graph --pretty=tformat:%s \"$@\" >actual.raw &&\n \tsed \"s/ *$//\" actual.raw >actual &&\n \ttest_cmp expect actual\n@@ -185,20 +185,21 @@ test_expect_success 'log --graph with right-skewed merge following a left-skewed\n \n \tcheck_graph --date-order <<-\\EOF\n \t* 4_H\n-\t|\\\n+\t|\\ \n \t| * 4_G\n-\t| |\\\n+\t| |\\ \n+\t| | * 4_C\n \t| * | 4_F\n-\t|/| |\n+\t|/| | \n \t| * | 4_E\n-\t| |\\ \\\n-\t| | * | 4_D\n-\t| |/ /\n-\t|/| |\n-\t| | * 4_C\n-\t| |/\n+\t| |\\ \\ \n+\t| | |/ \n+\t| |/| \n+\t| | * 4_D\n+\t| |/ \n+\t|/| \n \t| * 4_B\n-\t|/\n+\t|/ \n \t* 4_A\n \tEOF\n '\n@@ -221,21 +222,20 @@ test_expect_success 'log --graph with octopus merge with column joining its penu\n \n \tcheck_graph <<-\\EOF\n \t* 5_H\n-\t|\\\n+\t|\\ \n \t| *-. 5_G\n-\t| |\\ \\\n+\t| |\\ \\ \n \t| | | * 5_F\n \t| | * | 5_E\n-\t| |/|\\ \\\n-\t| |_|/ /\n-\t|/| | /\n-\t| | |/\n-\t* | | 5_D\n+\t| |/|\\ \\ \n+\t| |_|/ / \n+\t|/| | / \n+\t| | |/ \n \t| | * 5_C\n-\t| |/\n-\t|/|\n-\t| * 5_B\n-\t|/\n+\t| * | 5_B\n+\t| |/ \n+\t* / 5_D\n+\t|/ \n \t* 5_A\n \tEOF\n '\ndiff --git a/t/t6003-rev-list-topo-order.sh b/t/t6003-rev-list-topo-order.sh\nindex 24d1836f41..19cb79bc29 100755\n--- a/t/t6003-rev-list-topo-order.sh\n+++ b/t/t6003-rev-list-topo-order.sh\n@@ -87,12 +87,12 @@ c3\n c2\n c1\n b4\n-a3\n-a2\n-a1\n b3\n b2\n b1\n+a3\n+a2\n+a1\n a0\n l2\n l1\n@@ -105,15 +105,15 @@ l5\n l4\n l3\n a4\n-b4\n-a3\n-a2\n c3\n c2\n+c1\n+b4\n b3\n b2\n-c1\n b1\n+a3\n+a2\n a1\n a0\n l2\n@@ -127,12 +127,12 @@ l5\n l4\n l3\n a4\n-b4\n c3\n c2\n+c1\n+b4\n b3\n b2\n-c1\n b1\n a3\n a2\n@@ -205,12 +205,12 @@ c3\n c2\n c1\n b4\n-a3\n-a2\n-a1\n b3\n b2\n b1\n+a3\n+a2\n+a1\n a0\n l2\n EOF\n@@ -224,12 +224,12 @@ c3\n c2\n c1\n b4\n-a3\n-a2\n-a1\n b3\n b2\n b1\n+a3\n+a2\n+a1\n a0\n l2\n EOF\n@@ -237,10 +237,10 @@ EOF\n test_output_expect_success 'prune near topo' 'git rev-list --topo-order a4 ^c3' <> 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+\tcat >> expected <<-TESTDATA &&\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+\t| | | o $C3\n+\t| | |/ \n+\t| | o $C2\n+\to | $A2\n+\t|/ \n+\to $A1\n+\tTESTDATA\n \tgit rev-list --graph --boundary --all ^C3 > actual &&\n \ttest_cmp expected actual\n \t'\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex b24d850036..a6d389c4fd 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -339,6 +339,8 @@ test_expect_success 'rev-list: ancestry-path topo-order' '\n \trun_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6\n '\n \n+# TODO get rid of the \"sort\" below \n+# if commitGraph is enabled then sort_in_topological_order is not envoked\n test_expect_success 'rev-list: symmetric difference topo-order' '\n \tgit rev-parse \\\n \t\tcommit-6-6 commit-5-6 commit-4-6 \\\n@@ -349,8 +351,8 @@ test_expect_success 'rev-list: symmetric difference topo-order' '\n \t\tcommit-6-1 commit-5-1 commit-4-1 \\\n \t\tcommit-3-8 commit-2-8 commit-1-8 \\\n \t\tcommit-3-7 commit-2-7 commit-1-7 \\\n-\t>expect &&\n-\trun_three_modes git rev-list --topo-order commit-3-8...commit-6-6\n+\t| sort >expect &&\n+\trun_three_modes git rev-list --topo-order commit-3-8...commit-6-6 | sort\n '\n \n test_expect_success 'get_reachable_subset:all' '\n-- \ngitgitgadget\n"},{"id":"389357","messageId":"nycvar.QRO.7.76.6.2001071305330.46@tvgsbejvaqbjf.bet","threadId":"52579","inReplyTo":"542a02020c8578d0e004cb9c929bced8719b902a.1578393057.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/1] Preserve topological ordering after merges This modifies the algorithm of topopological ordering. The problem with the current algoritm is that it displays the graph below as follows","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2020-01-07T12:08:18Z","receivedAt":"2020-01-07T12:08:28Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Sergey,\n\nplease note that the commit message's first line should not be longer than\n76 characters per line, and it should be followed by an empty line. I\nthink that you forgot the empty line, looking at\nhttps://github.com/gitgitgadget/git/pull/514/commits/542a02020c8578d0e004cb9c929bced8719b902a\n\nCiao,\nJohannes\n\nOn Tue, 7 Jan 2020, Sergey Rudyshin via GitGitGadget wrote:\n\n> From: Sergey Rudyshin <540555@gmail.com>\n>\n> * E\n> |\\\n> | * D\n> | |\\\n> | |/\n> |/|\n> * | C\n> | * B\n> |/\n> * A\n>\n> commit B is placed between A and C, which is wrong\n> because E stays that D and B comes after C\n>\n> the only correct solution here is\n>\n> * E\n> |\\\n> | * D\n> | |\\\n> | |/\n> |/|\n> | * B\n> * | C\n> |/\n> * A\n>\n> while it seems that it contradicts to\n> D stating that C should be between D and B\n> The new algorithm solves this issue\n>\n> Here is an example:\n> * walk to to the root via \"first\" parents;\n> * go E -> C -> A;\n> * print A because it has no parents;\n> * step back to C;\n> * print C because it has no other parents;\n> * then step back to E;\n> * go D -> B -> A;\n> * do not print A because A is already printed;\n> * step back to B;\n> * print B;\n> * so on.\n>\n> This change makes option \"--topo-order\" obsolete, because\n> there is only one way to order parents of a single commit.\n> \"--date-order\" and \"--author-date-order\" are preserved and make sense\n> only for the case when multiple commits are given\n> to be able to sort those commits.\n>\n> Signed-off-by: Sergey Rudyshin <540555@gmail.com>\n> ---\n> Documentation/git-rev-list.txt | 4 +-\n> Documentation/rev-list-options.txt | 41 +++---\n> commit.c | 149 ++++++++++++++-------\n> commit.h | 4 +-\n> t/t4202-log.sh | 15 +--\n> t/t4215-log-skewed-merges.sh | 44 +++---\n> t/t6003-rev-list-topo-order.sh | 54 ++++----\n> t/t6012-rev-list-simplify.sh | 8 +-\n> t/t6016-rev-list-graph-simplify-history.sh | 41 +++---\n> t/t6600-test-reach.sh | 6 +-\n> 10 files changed, 214 insertions(+), 152 deletions(-)\n>\n> diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt\n> index 025c911436..ad1fda7a54 100644\n> --- a/Documentation/git-rev-list.txt\n> +++ b/Documentation/git-rev-list.txt\n> @@ -3,7 +3,7 @@ git-rev-list(1)\n>\n> NAME\n> ----\n> -git-rev-list - Lists commit objects in reverse chronological order\n> +git-rev-list - Lists commit objects in reverse topological order\n>\n>\n> SYNOPSIS\n> @@ -17,7 +17,7 @@ DESCRIPTION\n> List commits that are reachable by following the `parent` links from the\n> given commit(s), but exclude commits that are reachable from the one(s)\n> given with a '{caret}' in front of them. The output is given in reverse\n> -chronological order by default.\n> +topological order by default.\n>\n> You can think of this as a set operation. Commits given on the command\n> line form a set of commits that are reachable from any of them, and then\n> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> index bfd02ade99..7ab2f451ae 100644\n> --- a/Documentation/rev-list-options.txt\n> +++ b/Documentation/rev-list-options.txt\n> @@ -643,39 +643,42 @@ ifndef::git-shortlog[]\n> Commit Ordering\n> ~~~~~~~~~~~~~~~\n>\n> -By default, the commits are shown in reverse chronological order.\n> +By default, the commits are shown in reverse topological order.\n> ++\n> +Meaning that no parents are shown before all of its children and\n> +merges do not change the previous order.\n> ++\n> +E.g., if commit M0 produces topologically ordered list of\n> +commits L0 then commit M1 created by merging any commit into M0\n> +produces list L1 which starts with L0\n> ++\n> +In case if multiple commits are given via the command line\n> +the following parameters determine the order among them:\n>\n> --date-order::\n> -\tShow no parents before all of its children are shown, but\n> -\totherwise show commits in the commit timestamp order.\n> +\tshow commits in the commit timestamp order.\n>\n> --author-date-order::\n> -\tShow no parents before all of its children are shown, but\n> -\totherwise show commits in the author timestamp order.\n> +\tshow commits in the author timestamp order.\n>\n> --topo-order::\n> -\tShow no parents before all of its children are shown, and\n> -\tavoid showing commits on multiple lines of history\n> -\tintermixed.\n> +\tshow commits in the commit timestamp order.\n> +\tthis is deprecated and will be\n> +\tremoved in the future.\n> +\n> For example, in a commit history like this:\n> +\n> ----------------------------------------------------------------\n> -\n> - ---1----2----4----7\n> -\t\\\t \\\n> -\t 3----5----6----8---\n> -\n> + 1----2-----------5\n> + \\ \\ /\n> + -----\\---3---4---6\n> + \\ /\n> + ----\n> ----------------------------------------------------------------\n> +\n> where the numbers denote the order of commit timestamps, `git\n> rev-list` and friends with `--date-order` show the commits in the\n> -timestamp order: 8 7 6 5 4 3 2 1.\n> -+\n> -With `--topo-order`, they would show 8 6 5 3 7 4 2 1 (or 8 7 4 2 6 5\n> -3 1); some older commits are shown before newer ones in order to\n> -avoid showing the commits from two parallel development track mixed\n> -together.\n> +following order: 1 2 3 4 5 6.\n>\n> --reverse::\n> \tOutput the commits chosen to be shown (see Commit Limiting\n> diff --git a/commit.c b/commit.c\n> index 434ec030d6..01e9d07db9 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -738,6 +738,12 @@ int compare_commits_by_author_date(const void *a_, const void *b_,\n> \treturn 0;\n> }\n>\n> +static int compare_commits_by_author_date_rev(const void *a_, const void *b_,\n> +\t\t\t\t void *cb_data)\n> +{\n> +\treturn compare_commits_by_author_date(b_, a_, cb_data);\n> +}\n> +\n> int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)\n> {\n> \tconst struct commit *a = a_, *b = b_;\n> @@ -767,36 +773,83 @@ int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n> \treturn 0;\n> }\n>\n> +static int compare_commits_by_commit_date_rev(const void *a_, const void *b_, void *unused)\n> +{\n> +\treturn compare_commits_by_commit_date (b_, a_, unused);\n> +}\n> +\n> +struct maze {\n> +\tstruct commit *ret;\n> +\tstruct commit *out;\n> +};\n> +\n> +define_commit_slab(maze_slab, struct maze *);\n> +\n> +/*\n> + * returns the next commit while exploring the maze\n> + * current commit has the information:\n> + * \t- what was the last commit we went for (OUT)\n> + * \t- from which commit we came in (RET)\n> + * trying to find a parent next to OUT\n> + * if it does not exists returns RET\n> + * otherwise returns the found parent\n> + */\n> +static struct commit *get_next(struct commit *commit, struct maze *mz, struct indegree_slab *indegree)\n> +{\n> +\tstruct commit_list *parents = commit->parents;\n> +\tstruct commit *next = NULL;\n> +\tint found = 0;\n> +\n> +\twhile (parents) {\n> +\t\tstruct commit *parent = parents->item;\n> +\n> +\t\tif (*indegree_slab_at(indegree, parent)) {\n> +\n> +\t\t\tif (!mz->out || found) {\n> +\t\t\t\tnext = parent;\n> +\t\t\t\tbreak;\n> +\t\t\t} else if (mz->out == parent) {\n> +\t\t\t\tfound = 1;\n> +\t\t\t}\n> +\t\t}\n> +\t\tparents = parents->next;\n> +\t}\n> +\n> +\tif (!next) next = mz->ret;\n> +\n> +\treturn next;\n> +}\n> +\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> {\n> \tstruct commit_list *next, *orig = *list;\n> -\tstruct commit_list **pptr;\n> +\tstruct commit_list **pptr = list;\n> \tstruct indegree_slab indegree;\n> -\tstruct prio_queue queue;\n> +\tstruct prio_queue queue_tips;\n> \tstruct commit *commit;\n> \tstruct author_date_slab author_date;\n> +\tstruct maze_slab maze;\n> +\tstruct maze *mz;\n>\n> \tif (!orig)\n> \t\treturn;\n> \t*list = NULL;\n>\n> \tinit_indegree_slab(&indegree);\n> -\tmemset(&queue, '\\0', sizeof(queue));\n> +\tinit_maze_slab(&maze);\n> +\tmemset(&queue_tips, '\\0', sizeof(queue_tips));\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> +\tdefault:\n> +\t\tqueue_tips.compare = compare_commits_by_commit_date_rev;\n> \t\tbreak;\n> \tcase 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\tqueue_tips.compare = compare_commits_by_author_date_rev;\n> +\t\tqueue_tips.cb_data = &author_date;\n> \t\tbreak;\n> \t}\n>\n> @@ -804,9 +857,10 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n> \tfor (next = orig; next; next = next->next) {\n> \t\tstruct commit *commit = next->item;\n> \t\t*(indegree_slab_at(&indegree, commit)) = 1;\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\tmz = xmalloc(sizeof(struct maze));\n> +\t\tmz->ret = NULL;\n> +\t\tmz->out = NULL;\n> +\t\t*(maze_slab_at(&maze, commit)) = mz;\n> \t}\n>\n> \t/* update the indegree */\n> @@ -832,51 +886,56 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n> \tfor (next = orig; next; next = next->next) {\n> \t\tstruct commit *commit = next->item;\n>\n> -\t\tif (*(indegree_slab_at(&indegree, commit)) == 1)\n> -\t\t\tprio_queue_put(&queue, commit);\n> +\t\tif (*(indegree_slab_at(&indegree, commit)) == 1) {\n> +\t\t\t/* also record the author dates, if needed */\n> +\t\t\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n> +\t\t\t\trecord_author_date(&author_date, commit);\n> +\t\t\tprio_queue_put(&queue_tips, commit);\n> +\t\t}\n> \t}\n>\n> -\t/*\n> -\t * This is unfortunate; the initial tips need to be shown\n> -\t * in the order given from the revision traversal machinery.\n> -\t */\n> -\tif (sort_order == REV_SORT_IN_GRAPH_ORDER)\n> -\t\tprio_queue_reverse(&queue);\n> -\n> \t/* We no longer need the commit list */\n> \tfree_commit_list(orig);\n>\n> \tpptr = list;\n> \t*list = NULL;\n> -\twhile ((commit = prio_queue_get(&queue)) != NULL) {\n> -\t\tstruct commit_list *parents;\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>\n> -\t\t\tif (!*pi)\n> +\twhile ((commit = prio_queue_get(&queue_tips)) != NULL) {\n> +\t\tstruct commit *prev_commit = NULL;\n> +\t\twhile (commit) {\n> +\t\t\tmz = *(maze_slab_at(&maze, commit));\n> +\t\t\tif (!prev_commit) {\n> +\t\t\t\t/* either a new tip or\n> +\t\t\t\t * after entering an already visited commit\n> +\t\t\t\t */\n> +\t\t\t}\n> +\t\t\telse if (!mz->out) {\n> +\t\t\t\t/* happens only once for every commit\n> +\t\t\t\t * note that for tips RET is set to NULL\n> +\t\t\t\t */\n> +\t\t\t\tmz->ret = prev_commit;\n> +\t\t\t}\n> +\t\t\telse if (prev_commit != mz->out) {\n> +\t\t\t\t/* entered an already visited commit\n> +\t\t\t\t * step back\n> +\t\t\t\t */\n> +\t\t\t\tcommit = prev_commit;\n> +\t\t\t\tprev_commit = NULL;\n> \t\t\t\tcontinue;\n> -\n> -\t\t\t/*\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\tif (--(*pi) == 1)\n> -\t\t\t\tprio_queue_put(&queue, parent);\n> +\t\t\t}\n> +\t\t\tmz->out = get_next(commit, mz, &indegree);\n> +\t\t\tif (mz->out == mz->ret) {\n> +\t\t\t\t/* upon leaving a commit emit it */\n> +\t\t\t\t*pptr = commit_list_insert(commit, pptr);\n> +\t\t\t}\n> +\t\t\tprev_commit = commit;\n> +\t\t\tcommit = mz->out;\n> \t\t}\n> -\t\t/*\n> -\t\t * all children of commit have already been\n> -\t\t * emitted. we can emit it now.\n> -\t\t */\n> -\t\t*(indegree_slab_at(&indegree, commit)) = 0;\n> -\n> -\t\tpptr = &commit_list_insert(commit, pptr)->next;\n> \t}\n>\n> \tclear_indegree_slab(&indegree);\n> -\tclear_prio_queue(&queue);\n> +\tclear_maze_slab(&maze);\n> +\tclear_prio_queue(&queue_tips);\n> \tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n> \t\tclear_author_date_slab(&author_date);\n> }\n> diff --git a/commit.h b/commit.h\n> index 221cdaa34b..1fe3cc240e 100644\n> --- a/commit.h\n> +++ b/commit.h\n> @@ -209,7 +209,7 @@ struct commit *pop_commit(struct commit_list **stack);\n> void clear_commit_marks(struct commit *commit, unsigned int mark);\n> void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark);\n>\n> -\n> +/* TODO get rid of rev_sort_order in a favour of positional parameters */\n> enum rev_sort_order {\n> \tREV_SORT_IN_GRAPH_ORDER = 0,\n> \tREV_SORT_BY_COMMIT_DATE,\n> @@ -222,8 +222,6 @@ enum rev_sort_order {\n> * invariant of resulting list is:\n> * a reachable from b => ord(b) < ord(a)\n> * sort_order further specifies:\n> - * REV_SORT_IN_GRAPH_ORDER: try to show a commit on a single-parent\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> diff --git a/t/t4202-log.sh b/t/t4202-log.sh\n> index 2c9489484a..46f04b36a3 100755\n> --- a/t/t4202-log.sh\n> +++ b/t/t4202-log.sh\n> @@ -635,17 +635,16 @@ test_expect_success 'set up more tangled history' '\n> cat > expect <<\\EOF\n> * Merge tag 'reach'\n> |\\\n> -| \\\n> +| * reach\n> +| |\n> | \\\n> *-. \\ Merge tags 'octopus-a' and 'octopus-b'\n> |\\ \\ \\\n> -* | | | seventh\n> | | * | octopus-b\n> -| |/ /\n> -|/| |\n> -| * | octopus-a\n> -|/ /\n> -| * reach\n> +| | |/\n> +| * / octopus-a\n> +| |/\n> +* / seventh\n> |/\n> * Merge branch 'tangle'\n> |\\\n> @@ -673,7 +672,7 @@ cat > expect <<\\EOF\n> * initial\n> EOF\n>\n> -test_expect_success 'log --graph with merge' '\n> +test_expect_success 'log --graph with merge tag reach' '\n> \tgit log --graph --date-order --pretty=tformat:%s |\n> \t\tsed \"s/ *\\$//\" >actual &&\n> \ttest_cmp expect actual\n> diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh\n> index 18709a723e..91630c0cae 100755\n> --- a/t/t4215-log-skewed-merges.sh\n> +++ b/t/t4215-log-skewed-merges.sh\n> @@ -5,7 +5,7 @@ test_description='git log --graph of skewed merges'\n> . ./test-lib.sh\n>\n> check_graph () {\n> -\tcat >expect &&\n> +\tsed \"s/ *$//\" >expect &&\n> \tgit log --graph --pretty=tformat:%s \"$@\" >actual.raw &&\n> \tsed \"s/ *$//\" actual.raw >actual &&\n> \ttest_cmp expect actual\n> @@ -185,20 +185,21 @@ test_expect_success 'log --graph with right-skewed merge following a left-skewed\n>\n> \tcheck_graph --date-order <<-\\EOF\n> \t* 4_H\n> -\t|\\\n> +\t|\\\n> \t| * 4_G\n> -\t| |\\\n> +\t| |\\\n> +\t| | * 4_C\n> \t| * | 4_F\n> -\t|/| |\n> +\t|/| |\n> \t| * | 4_E\n> -\t| |\\ \\\n> -\t| | * | 4_D\n> -\t| |/ /\n> -\t|/| |\n> -\t| | * 4_C\n> -\t| |/\n> +\t| |\\ \\\n> +\t| | |/\n> +\t| |/|\n> +\t| | * 4_D\n> +\t| |/\n> +\t|/|\n> \t| * 4_B\n> -\t|/\n> +\t|/\n> \t* 4_A\n> \tEOF\n> '\n> @@ -221,21 +222,20 @@ test_expect_success 'log --graph with octopus merge with column joining its penu\n>\n> \tcheck_graph <<-\\EOF\n> \t* 5_H\n> -\t|\\\n> +\t|\\\n> \t| *-. 5_G\n> -\t| |\\ \\\n> +\t| |\\ \\\n> \t| | | * 5_F\n> \t| | * | 5_E\n> -\t| |/|\\ \\\n> -\t| |_|/ /\n> -\t|/| | /\n> -\t| | |/\n> -\t* | | 5_D\n> +\t| |/|\\ \\\n> +\t| |_|/ /\n> +\t|/| | /\n> +\t| | |/\n> \t| | * 5_C\n> -\t| |/\n> -\t|/|\n> -\t| * 5_B\n> -\t|/\n> +\t| * | 5_B\n> +\t| |/\n> +\t* / 5_D\n> +\t|/\n> \t* 5_A\n> \tEOF\n> '\n> diff --git a/t/t6003-rev-list-topo-order.sh b/t/t6003-rev-list-topo-order.sh\n> index 24d1836f41..19cb79bc29 100755\n> --- a/t/t6003-rev-list-topo-order.sh\n> +++ b/t/t6003-rev-list-topo-order.sh\n> @@ -87,12 +87,12 @@ c3\n> c2\n> c1\n> b4\n> -a3\n> -a2\n> -a1\n> b3\n> b2\n> b1\n> +a3\n> +a2\n> +a1\n> a0\n> l2\n> l1\n> @@ -105,15 +105,15 @@ l5\n> l4\n> l3\n> a4\n> -b4\n> -a3\n> -a2\n> c3\n> c2\n> +c1\n> +b4\n> b3\n> b2\n> -c1\n> b1\n> +a3\n> +a2\n> a1\n> a0\n> l2\n> @@ -127,12 +127,12 @@ l5\n> l4\n> l3\n> a4\n> -b4\n> c3\n> c2\n> +c1\n> +b4\n> b3\n> b2\n> -c1\n> b1\n> a3\n> a2\n> @@ -205,12 +205,12 @@ c3\n> c2\n> c1\n> b4\n> -a3\n> -a2\n> -a1\n> b3\n> b2\n> b1\n> +a3\n> +a2\n> +a1\n> a0\n> l2\n> EOF\n> @@ -224,12 +224,12 @@ c3\n> c2\n> c1\n> b4\n> -a3\n> -a2\n> -a1\n> b3\n> b2\n> b1\n> +a3\n> +a2\n> +a1\n> a0\n> l2\n> EOF\n> @@ -237,10 +237,10 @@ EOF\n> test_output_expect_success 'prune near topo' 'git rev-list --topo-order a4 ^c3' < a4\n> b4\n> +b3\n> a3\n> a2\n> a1\n> -b3\n> EOF\n>\n> test_output_expect_success \"head has no parent\" 'git rev-list --topo-order root' < @@ -297,8 +297,8 @@ c3\n> c2\n> c1\n> b4\n> -a3\n> -a2\n> +b3\n> +b2\n> EOF\n>\n> test_output_expect_success \"max-count 10 - non topo order\" 'git rev-list --max-count=10 l5' < @@ -376,12 +376,12 @@ c3\n> c2\n> c1\n> b4\n> -a3\n> -a2\n> -a1\n> b3\n> b2\n> b1\n> +a3\n> +a2\n> +a1\n> a0\n> l2\n> l1\n> @@ -399,12 +399,12 @@ c3\n> c2\n> c1\n> b4\n> -a3\n> -a2\n> -a1\n> b3\n> b2\n> b1\n> +a3\n> +a2\n> +a1\n> a0\n> l2\n> l1\n> @@ -428,12 +428,12 @@ c3\n> c2\n> c1\n> b4\n> -a3\n> -a2\n> -a1\n> b3\n> b2\n> b1\n> +a3\n> +a2\n> +a1\n> a0\n> l2\n> l1\n> diff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh\n> index a10f0df02b..9f687b6b22 100755\n> --- a/t/t6012-rev-list-simplify.sh\n> +++ b/t/t6012-rev-list-simplify.sh\n> @@ -122,16 +122,16 @@ check_result () {\n>\n> check_result 'L K J I H F E D C G B A' --full-history --topo-order\n> check_result 'L K I H G F E D C B J A' --full-history\n> -check_result 'L K I H G F E D C B J A' --full-history --date-order\n> -check_result 'L K I H G F E D B C J A' --full-history --author-date-order\n> +check_result 'L K J I H F E D C G B A' --full-history --date-order\n> +check_result 'L K J I H F E D C G B A' --full-history --author-date-order\n> check_result 'K I H E C B A' --full-history -- file\n> check_result 'K I H E C B A' --full-history --topo-order -- file\n> check_result 'K I H E C B A' --full-history --date-order -- file\n> -check_result 'K I H E B C A' --full-history --author-date-order -- file\n> +check_result 'K I H E C B A' --full-history --author-date-order -- file\n> check_result 'I E C B A' --simplify-merges -- file\n> check_result 'I E C B A' --simplify-merges --topo-order -- file\n> check_result 'I E C B A' --simplify-merges --date-order -- file\n> -check_result 'I E B C A' --simplify-merges --author-date-order -- file\n> +check_result 'I E C B A' --simplify-merges --author-date-order -- file\n> check_result 'I B A' -- file\n> check_result 'I B A' --topo-order -- file\n> check_result 'I B A' --date-order -- file\n> diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh\n> index f5e6e92f5b..5750c6f0fd 100755\n> --- a/t/t6016-rev-list-graph-simplify-history.sh\n> +++ b/t/t6016-rev-list-graph-simplify-history.sh\n> @@ -235,27 +235,28 @@ test_expect_success '--graph ^C3' '\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> +test_expect_success '--graph --boundary --all ^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> +\tcat >> expected <<-TESTDATA &&\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> +\t| | | o $C3\n> +\t| | |/\n> +\t| | o $C2\n> +\to | $A2\n> +\t|/\n> +\to $A1\n> +\tTESTDATA\n> \tgit rev-list --graph --boundary --all ^C3 > actual &&\n> \ttest_cmp expected actual\n> \t'\n> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\n> index b24d850036..a6d389c4fd 100755\n> --- a/t/t6600-test-reach.sh\n> +++ b/t/t6600-test-reach.sh\n> @@ -339,6 +339,8 @@ test_expect_success 'rev-list: ancestry-path topo-order' '\n> \trun_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6\n> '\n>\n> +# TODO get rid of the \"sort\" below\n> +# if commitGraph is enabled then sort_in_topological_order is not envoked\n> test_expect_success 'rev-list: symmetric difference topo-order' '\n> \tgit rev-parse \\\n> \t\tcommit-6-6 commit-5-6 commit-4-6 \\\n> @@ -349,8 +351,8 @@ test_expect_success 'rev-list: symmetric difference topo-order' '\n> \t\tcommit-6-1 commit-5-1 commit-4-1 \\\n> \t\tcommit-3-8 commit-2-8 commit-1-8 \\\n> \t\tcommit-3-7 commit-2-7 commit-1-7 \\\n> -\t>expect &&\n> -\trun_three_modes git rev-list --topo-order commit-3-8...commit-6-6\n> +\t| sort >expect &&\n> +\trun_three_modes git rev-list --topo-order commit-3-8...commit-6-6 | sort\n> '\n>\n> test_expect_success 'get_reachable_subset:all' '\n> --\n> gitgitgadget\n>\n>\n"},{"id":"389358","messageId":"nycvar.QRO.7.76.6.2001071308290.46@tvgsbejvaqbjf.bet","threadId":"52579","inReplyTo":"pull.514.git.1578393057.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/1] Preserve topological ordering after merges","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2020-01-07T12:11:41Z","receivedAt":"2020-01-07T12:11:48Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Sergey,\n\nOn Tue, 7 Jan 2020, Sergey Rudyshin via GitGitGadget wrote:\n\n> This modifies the algoritm of topopological ordering. The problem with the\n> current algoritm is that it displays the graph below as following\n>\n> * E\n> |\\\n> | * D\n> | |\\\n> | |/\n> |/|\n> * | C\n> | * B\n> |/\n> * A\n>\n> commit B is placed between A and C, which is wrong because E stays that D\n> and B comes after C\n>\n> the only correct solution here is\n>\n> * E\n> |\\\n> | * D\n> | |\\\n> | |/\n> |/|\n> | * B\n> * | C\n> |/\n> * A\n>\n> while it seems that it contradicts to D staiting that C shoud be between D\n> and B The new algorithm solves this issue\n>\n> Here is an example: walk to to the root via \"first\" parents go E -> C -> A\n> print A because it has no parents step back to C print C because it has no\n> other parents then step back to E go D -> B -> A do not print A becase A is\n> already printed step back to B print B so on\n>\n> This change makes option \"--topo-order\" obsolete, because for a single\n> commit there is only one way to order parents. \"--date-order\" and\n> \"--author-date-order\" are preserved and make sence only for the case when\n> multiple commits are given to be able to sort those commits.\n\nI have to admit that I am not a fan of this change, as I find that there\nare legitimate use cases where I want to order the commits by commit\ntopology, and other use cases where I want to order them by date.\n\nMaybe other reviewers agree with your reasoning, though, in that case you\nstill will need to address the test failures in t4202, t4215 and t6012:\nhttps://dev.azure.com/gitgitgadget/git/_build/results?buildId=25867&view=ms.vss-test-web.build-test-results-tab\n\nCiao,\nJohannes\n\n>\n> Sergey Rudyshin (1):\n> Preserve topological ordering after merges This modifies the algorithm\n> of topopological ordering. The problem with the current algoritm is\n> that it displays the graph below as follows\n>\n> Documentation/git-rev-list.txt | 4 +-\n> Documentation/rev-list-options.txt | 41 +++---\n> commit.c | 149 ++++++++++++++-------\n> commit.h | 4 +-\n> t/t4202-log.sh | 15 +--\n> t/t4215-log-skewed-merges.sh | 44 +++---\n> t/t6003-rev-list-topo-order.sh | 54 ++++----\n> t/t6012-rev-list-simplify.sh | 8 +-\n> t/t6016-rev-list-graph-simplify-history.sh | 41 +++---\n> t/t6600-test-reach.sh | 6 +-\n> 10 files changed, 214 insertions(+), 152 deletions(-)\n>\n>\n> base-commit: 8679ef24ed64018bb62170c43ce73e0261c0600a\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-514%2FSergeyRudyshin%2Ftopo_order_fix-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-514/SergeyRudyshin/topo_order_fix-v1\n> Pull-Request: https://github.com/gitgitgadget/git/pull/514\n> --\n> gitgitgadget\n>\n"},{"id":"389359","messageId":"6c86f1e9-b70b-10b1-f2c5-589312f73a4c@gmail.com","threadId":"52579","inReplyTo":"542a02020c8578d0e004cb9c929bced8719b902a.1578393057.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/1] Preserve topological ordering after merges This modifies the algorithm of topopological ordering. The problem with the current algoritm is that it displays the graph below as follows","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-01-07T12:14:29Z","receivedAt":"2020-01-07T12:14:34Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/7/2020 5:30 AM, Sergey Rudyshin via GitGitGadget wrote:\n> From: Sergey Rudyshin <540555@gmail.com>\n> \n> * E\n> |\\\n> | * D\n> | |\\\n> | |/\n> |/|\n> * | C\n> | * B\n> |/\n> * A\n> \n> commit B is placed between A and C, which is wrong\n> because E stays that D and B comes after C\n> \n> the only correct solution here is\n> \n> * E\n> |\\\n> | * D\n> | |\\\n> | |/\n> |/|\n> | * B\n> * | C\n> |/\n> * A\n> \n> while it seems that it contradicts to\n> D stating that C should be between D and B\n> The new algorithm solves this issue\n\nThis ordering concern makes sense _somewhat_, because D is the\nsecond parent of D and that wants to say \"Show everything in C..D\nbefore showing C\". The issues is that since C is the second parent\nof D, the topo-ordering says \"Show everything in B..C before showing\nthings reachable from B\". It is unfortunate that these constraints\ncollide.\n\nPerhaps your description could do a better job clarifying this\nissue and how your algorithm change fixes the problem.\n\nHowever, I'm not sure we even want to make the change, as this\nis still a valid topological order (parents appear after children).\nWhen we have an ambiguous pair (like B and C) the order can differ.\nThe --topo-order option tries to group commits by when they were\nintroduced, and that's the reason for presenting the commits reachable\nfrom the later parents before presenting the commits from earlier\nparents.\n\nThe only documentation we have is from [1]:\n\n\"Show no parents before all of its children are shown, and avoid\nshowing commits on multiple lines of history intermixed.\"\n\nThe first part of the sentence is still true, and the second part\nis ambiguous of how to do that.\n\n[1] https://git-scm.com/docs/git-log#Documentation/git-log.txt---topo-order\n\n> This change makes option \"--topo-order\" obsolete, because\n> there is only one way to order parents of a single commit.\n> \"--date-order\" and \"--author-date-order\" are preserved and make sense\n> only for the case when multiple commits are given\n> to be able to sort those commits.\n\nThis part of the change needs to be removed. The default sort does\nnot preserve topological orderings (like --date-order does), and\nso is much faster to output, especially without a commit-graph file.\n\n> void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order)\n\nSince you are only editing this code, and not the incremental topo-order code, your\ntest changes will likely break when run with GIT_TEST_COMMIT_GRAPH=1. When the commit-graph\nexists and generation numbers are calculated, we use a different algorithm for topo-order.\n\nI've been meaning to clean up this \"duplicated\" logic by deleting this method in favor of\nthe incremental algorithm in all cases. It needs some perf testing to make sure that\nrefactor doesn't have too large of a perf hit in the case of no commit-graph.\n\n> \t/* update the indegree */\n> @@ -832,51 +886,56 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n> \tfor (next = orig; next; next = next->next) {\n> \t\tstruct commit *commit = next->item;\n> \n> -\t\tif (*(indegree_slab_at(&indegree, commit)) == 1)\n> -\t\t\tprio_queue_put(&queue, commit);\n> +\t\tif (*(indegree_slab_at(&indegree, commit)) == 1) {\n> +\t\t\t/* also record the author dates, if needed */\n> +\t\t\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n> +\t\t\t\trecord_author_date(&author_date, commit);\n> +\t\t\tprio_queue_put(&queue_tips, commit);\n> +\t\t}\n\nYour code change looks rather large for what I expected to be a much simpler change.\nLikely the only thing we need is to avoid adding to the priority queue if we already\nhave the commit in the queue (maybe using a hashset storing the commits that we've\nadded to the queue). I believe the reason C appears before B in your example is that\nit was added to the queue a second time, and the queue behaves like a stack in the\ntopo-order case.\n\nThanks,\n-Stolee\n"},{"id":"389398","messageId":"xmqqr20b5hfq.fsf@gitster-ct.c.googlers.com","threadId":"52579","inReplyTo":"nycvar.QRO.7.76.6.2001071305330.46@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 1/1] Preserve topological ordering after merges This modifies the algorithm of topopological ordering. The problem with the current algoritm is that it displays the graph below as follows","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-01-07T17:01:45Z","receivedAt":"2020-01-07T17:01:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> Hi Sergey,\n>\n> please note that the commit message's first line should not be longer than\n> 76 characters per line, and it should be followed by an empty line. I\n> think that you forgot the empty line, looking at\n> https://github.com/gitgitgadget/git/pull/514/commits/542a02020c8578d0e004cb9c929bced8719b902a\n\nThanks for a good suggestion.\n\nAlso, please do *not* CC iterations of a patch to me that hasn't\nseen a concensus that it is a good idea on the list yet, unless\nyou know I am the area expert and am interested in seeing it.\n\nThanks.\n"},{"id":"389456","messageId":"CAFQTW8DhR4Zqvyq0S_9vhUOqvG2eE7fD62yKc_u130MHtCfz8Q@mail.gmail.com","threadId":"52579","inReplyTo":"nycvar.QRO.7.76.6.2001071305330.46@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 1/1] Preserve topological ordering after merges This modifies the algorithm of topopological ordering. The problem with the current algoritm is that it displays the graph below as follows","fromName":"Sergey Rudyshin","fromEmail":"540555@gmail.com","sentAt":"2020-01-08T07:51:38Z","receivedAt":"2020-01-08T07:51:53Z","isPatch":true,"sender":{"key":"540555@gmail.com","avatar":null},"body":"Hi, Johannes,\nthank you for your comment\nIndeed i forgot to put an emty line. Will fix it.\n\nOn Tue, Jan 7, 2020 at 3:08 PM Johannes Schindelin\n wrote:\n>\n> Hi Sergey,\n>\n> please note that the commit message's first line should not be longer than\n> 76 characters per line, and it should be followed by an empty line. I\n> think that you forgot the empty line, looking at\n> https://github.com/gitgitgadget/git/pull/514/commits/542a02020c8578d0e004cb9c929bced8719b902a\n>\n> Ciao,\n> Johannes\n>\n> On Tue, 7 Jan 2020, Sergey Rudyshin via GitGitGadget wrote:\n>\n> > From: Sergey Rudyshin <540555@gmail.com>\n> >\n> > * E\n> > |\\\n> > | * D\n> > | |\\\n> > | |/\n> > |/|\n> > * | C\n> > | * B\n> > |/\n> > * A\n> >\n> > commit B is placed between A and C, which is wrong\n> > because E stays that D and B comes after C\n> >\n> > the only correct solution here is\n> >\n> > * E\n> > |\\\n> > | * D\n> > | |\\\n> > | |/\n> > |/|\n> > | * B\n> > * | C\n> > |/\n> > * A\n> >\n> > while it seems that it contradicts to\n> > D stating that C should be between D and B\n> > The new algorithm solves this issue\n> >\n> > Here is an example:\n> > * walk to to the root via \"first\" parents;\n> > * go E -> C -> A;\n> > * print A because it has no parents;\n> > * step back to C;\n> > * print C because it has no other parents;\n> > * then step back to E;\n> > * go D -> B -> A;\n> > * do not print A because A is already printed;\n> > * step back to B;\n> > * print B;\n> > * so on.\n> >\n> > This change makes option \"--topo-order\" obsolete, because\n> > there is only one way to order parents of a single commit.\n> > \"--date-order\" and \"--author-date-order\" are preserved and make sense\n> > only for the case when multiple commits are given\n> > to be able to sort those commits.\n> >\n> > Signed-off-by: Sergey Rudyshin <540555@gmail.com>\n> > ---\n> > Documentation/git-rev-list.txt | 4 +-\n> > Documentation/rev-list-options.txt | 41 +++---\n> > commit.c | 149 ++++++++++++++-------\n> > commit.h | 4 +-\n> > t/t4202-log.sh | 15 +--\n> > t/t4215-log-skewed-merges.sh | 44 +++---\n> > t/t6003-rev-list-topo-order.sh | 54 ++++----\n> > t/t6012-rev-list-simplify.sh | 8 +-\n> > t/t6016-rev-list-graph-simplify-history.sh | 41 +++---\n> > t/t6600-test-reach.sh | 6 +-\n> > 10 files changed, 214 insertions(+), 152 deletions(-)\n> >\n> > diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt\n> > index 025c911436..ad1fda7a54 100644\n> > --- a/Documentation/git-rev-list.txt\n> > +++ b/Documentation/git-rev-list.txt\n> > @@ -3,7 +3,7 @@ git-rev-list(1)\n> >\n> > NAME\n> > ----\n> > -git-rev-list - Lists commit objects in reverse chronological order\n> > +git-rev-list - Lists commit objects in reverse topological order\n> >\n> >\n> > SYNOPSIS\n> > @@ -17,7 +17,7 @@ DESCRIPTION\n> > List commits that are reachable by following the `parent` links from the\n> > given commit(s), but exclude commits that are reachable from the one(s)\n> > given with a '{caret}' in front of them. The output is given in reverse\n> > -chronological order by default.\n> > +topological order by default.\n> >\n> > You can think of this as a set operation. Commits given on the command\n> > line form a set of commits that are reachable from any of them, and then\n> > diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> > index bfd02ade99..7ab2f451ae 100644\n> > --- a/Documentation/rev-list-options.txt\n> > +++ b/Documentation/rev-list-options.txt\n> > @@ -643,39 +643,42 @@ ifndef::git-shortlog[]\n> > Commit Ordering\n> > ~~~~~~~~~~~~~~~\n> >\n> > -By default, the commits are shown in reverse chronological order.\n> > +By default, the commits are shown in reverse topological order.\n> > ++\n> > +Meaning that no parents are shown before all of its children and\n> > +merges do not change the previous order.\n> > ++\n> > +E.g., if commit M0 produces topologically ordered list of\n> > +commits L0 then commit M1 created by merging any commit into M0\n> > +produces list L1 which starts with L0\n> > ++\n> > +In case if multiple commits are given via the command line\n> > +the following parameters determine the order among them:\n> >\n> > --date-order::\n> > - Show no parents before all of its children are shown, but\n> > - otherwise show commits in the commit timestamp order.\n> > + show commits in the commit timestamp order.\n> >\n> > --author-date-order::\n> > - Show no parents before all of its children are shown, but\n> > - otherwise show commits in the author timestamp order.\n> > + show commits in the author timestamp order.\n> >\n> > --topo-order::\n> > - Show no parents before all of its children are shown, and\n> > - avoid showing commits on multiple lines of history\n> > - intermixed.\n> > + show commits in the commit timestamp order.\n> > + this is deprecated and will be\n> > + removed in the future.\n> > +\n> > For example, in a commit history like this:\n> > +\n> > ----------------------------------------------------------------\n> > -\n> > - ---1----2----4----7\n> > - \\ \\\n> > - 3----5----6----8---\n> > -\n> > + 1----2-----------5\n> > + \\ \\ /\n> > + -----\\---3---4---6\n> > + \\ /\n> > + ----\n> > ----------------------------------------------------------------\n> > +\n> > where the numbers denote the order of commit timestamps, `git\n> > rev-list` and friends with `--date-order` show the commits in the\n> > -timestamp order: 8 7 6 5 4 3 2 1.\n> > -+\n> > -With `--topo-order`, they would show 8 6 5 3 7 4 2 1 (or 8 7 4 2 6 5\n> > -3 1); some older commits are shown before newer ones in order to\n> > -avoid showing the commits from two parallel development track mixed\n> > -together.\n> > +following order: 1 2 3 4 5 6.\n> >\n> > --reverse::\n> > Output the commits chosen to be shown (see Commit Limiting\n> > diff --git a/commit.c b/commit.c\n> > index 434ec030d6..01e9d07db9 100644\n> > --- a/commit.c\n> > +++ b/commit.c\n> > @@ -738,6 +738,12 @@ int compare_commits_by_author_date(const void *a_, const void *b_,\n> > return 0;\n> > }\n> >\n> > +static int compare_commits_by_author_date_rev(const void *a_, const void *b_,\n> > + void *cb_data)\n> > +{\n> > + return compare_commits_by_author_date(b_, a_, cb_data);\n> > +}\n> > +\n> > int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)\n> > {\n> > const struct commit *a = a_, *b = b_;\n> > @@ -767,36 +773,83 @@ int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n> > return 0;\n> > }\n> >\n> > +static int compare_commits_by_commit_date_rev(const void *a_, const void *b_, void *unused)\n> > +{\n> > + return compare_commits_by_commit_date (b_, a_, unused);\n> > +}\n> > +\n> > +struct maze {\n> > + struct commit *ret;\n> > + struct commit *out;\n> > +};\n> > +\n> > +define_commit_slab(maze_slab, struct maze *);\n> > +\n> > +/*\n> > + * returns the next commit while exploring the maze\n> > + * current commit has the information:\n> > + * - what was the last commit we went for (OUT)\n> > + * - from which commit we came in (RET)\n> > + * trying to find a parent next to OUT\n> > + * if it does not exists returns RET\n> > + * otherwise returns the found parent\n> > + */\n> > +static struct commit *get_next(struct commit *commit, struct maze *mz, struct indegree_slab *indegree)\n> > +{\n> > + struct commit_list *parents = commit->parents;\n> > + struct commit *next = NULL;\n> > + int found = 0;\n> > +\n> > + while (parents) {\n> > + struct commit *parent = parents->item;\n> > +\n> > + if (*indegree_slab_at(indegree, parent)) {\n> > +\n> > + if (!mz->out || found) {\n> > + next = parent;\n> > + break;\n> > + } else if (mz->out == parent) {\n> > + found = 1;\n> > + }\n> > + }\n> > + parents = parents->next;\n> > + }\n> > +\n> > + if (!next) next = mz->ret;\n> > +\n> > + return next;\n> > +}\n> > +\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> > {\n> > struct commit_list *next, *orig = *list;\n> > - struct commit_list **pptr;\n> > + struct commit_list **pptr = list;\n> > struct indegree_slab indegree;\n> > - struct prio_queue queue;\n> > + struct prio_queue queue_tips;\n> > struct commit *commit;\n> > struct author_date_slab author_date;\n> > + struct maze_slab maze;\n> > + struct maze *mz;\n> >\n> > if (!orig)\n> > return;\n> > *list = NULL;\n> >\n> > init_indegree_slab(&indegree);\n> > - memset(&queue, '\\0', sizeof(queue));\n> > + init_maze_slab(&maze);\n> > + memset(&queue_tips, '\\0', sizeof(queue_tips));\n> >\n> > switch (sort_order) {\n> > - default: /* REV_SORT_IN_GRAPH_ORDER */\n> > - queue.compare = NULL;\n> > - break;\n> > - case REV_SORT_BY_COMMIT_DATE:\n> > - queue.compare = compare_commits_by_commit_date;\n> > + default:\n> > + queue_tips.compare = compare_commits_by_commit_date_rev;\n> > break;\n> > case REV_SORT_BY_AUTHOR_DATE:\n> > init_author_date_slab(&author_date);\n> > - queue.compare = compare_commits_by_author_date;\n> > - queue.cb_data = &author_date;\n> > + queue_tips.compare = compare_commits_by_author_date_rev;\n> > + queue_tips.cb_data = &author_date;\n> > break;\n> > }\n> >\n> > @@ -804,9 +857,10 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n> > for (next = orig; next; next = next->next) {\n> > struct commit *commit = next->item;\n> > *(indegree_slab_at(&indegree, commit)) = 1;\n> > - /* also record the author dates, if needed */\n> > - if (sort_order == REV_SORT_BY_AUTHOR_DATE)\n> > - record_author_date(&author_date, commit);\n> > + mz = xmalloc(sizeof(struct maze));\n> > + mz->ret = NULL;\n> > + mz->out = NULL;\n> > + *(maze_slab_at(&maze, commit)) = mz;\n> > }\n> >\n> > /* update the indegree */\n> > @@ -832,51 +886,56 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n> > for (next = orig; next; next = next->next) {\n> > struct commit *commit = next->item;\n> >\n> > - if (*(indegree_slab_at(&indegree, commit)) == 1)\n> > - prio_queue_put(&queue, commit);\n> > + if (*(indegree_slab_at(&indegree, commit)) == 1) {\n> > + /* also record the author dates, if needed */\n> > + if (sort_order == REV_SORT_BY_AUTHOR_DATE)\n> > + record_author_date(&author_date, commit);\n> > + prio_queue_put(&queue_tips, commit);\n> > + }\n> > }\n> >\n> > - /*\n> > - * This is unfortunate; the initial tips need to be shown\n> > - * in the order given from the revision traversal machinery.\n> > - */\n> > - if (sort_order == REV_SORT_IN_GRAPH_ORDER)\n> > - prio_queue_reverse(&queue);\n> > -\n> > /* We no longer need the commit list */\n> > free_commit_list(orig);\n> >\n> > pptr = list;\n> > *list = NULL;\n> > - while ((commit = prio_queue_get(&queue)) != NULL) {\n> > - struct commit_list *parents;\n> > -\n> > - for (parents = commit->parents; parents ; parents = parents->next) {\n> > - struct commit *parent = parents->item;\n> > - int *pi = indegree_slab_at(&indegree, parent);\n> >\n> > - if (!*pi)\n> > + while ((commit = prio_queue_get(&queue_tips)) != NULL) {\n> > + struct commit *prev_commit = NULL;\n> > + while (commit) {\n> > + mz = *(maze_slab_at(&maze, commit));\n> > + if (!prev_commit) {\n> > + /* either a new tip or\n> > + * after entering an already visited commit\n> > + */\n> > + }\n> > + else if (!mz->out) {\n> > + /* happens only once for every commit\n> > + * note that for tips RET is set to NULL\n> > + */\n> > + mz->ret = prev_commit;\n> > + }\n> > + else if (prev_commit != mz->out) {\n> > + /* entered an already visited commit\n> > + * step back\n> > + */\n> > + commit = prev_commit;\n> > + prev_commit = NULL;\n> > continue;\n> > -\n> > - /*\n> > - * parents are only enqueued for emission\n> > - * when all their children have been emitted thereby\n> > - * guaranteeing topological order.\n> > - */\n> > - if (--(*pi) == 1)\n> > - prio_queue_put(&queue, parent);\n> > + }\n> > + mz->out = get_next(commit, mz, &indegree);\n> > + if (mz->out == mz->ret) {\n> > + /* upon leaving a commit emit it */\n> > + *pptr = commit_list_insert(commit, pptr);\n> > + }\n> > + prev_commit = commit;\n> > + commit = mz->out;\n> > }\n> > - /*\n> > - * all children of commit have already been\n> > - * emitted. we can emit it now.\n> > - */\n> > - *(indegree_slab_at(&indegree, commit)) = 0;\n> > -\n> > - pptr = &commit_list_insert(commit, pptr)->next;\n> > }\n> >\n> > clear_indegree_slab(&indegree);\n> > - clear_prio_queue(&queue);\n> > + clear_maze_slab(&maze);\n> > + clear_prio_queue(&queue_tips);\n> > if (sort_order == REV_SORT_BY_AUTHOR_DATE)\n> > clear_author_date_slab(&author_date);\n> > }\n> > diff --git a/commit.h b/commit.h\n> > index 221cdaa34b..1fe3cc240e 100644\n> > --- a/commit.h\n> > +++ b/commit.h\n> > @@ -209,7 +209,7 @@ struct commit *pop_commit(struct commit_list **stack);\n> > void clear_commit_marks(struct commit *commit, unsigned int mark);\n> > void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark);\n> >\n> > -\n> > +/* TODO get rid of rev_sort_order in a favour of positional parameters */\n> > enum rev_sort_order {\n> > REV_SORT_IN_GRAPH_ORDER = 0,\n> > REV_SORT_BY_COMMIT_DATE,\n> > @@ -222,8 +222,6 @@ enum rev_sort_order {\n> > * invariant of resulting list is:\n> > * a reachable from b => ord(b) < ord(a)\n> > * sort_order further specifies:\n> > - * REV_SORT_IN_GRAPH_ORDER: try to show a commit on a single-parent\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> > diff --git a/t/t4202-log.sh b/t/t4202-log.sh\n> > index 2c9489484a..46f04b36a3 100755\n> > --- a/t/t4202-log.sh\n> > +++ b/t/t4202-log.sh\n> > @@ -635,17 +635,16 @@ test_expect_success 'set up more tangled history' '\n> > cat > expect <<\\EOF\n> > * Merge tag 'reach'\n> > |\\\n> > -| \\\n> > +| * reach\n> > +| |\n> > | \\\n> > *-. \\ Merge tags 'octopus-a' and 'octopus-b'\n> > |\\ \\ \\\n> > -* | | | seventh\n> > | | * | octopus-b\n> > -| |/ /\n> > -|/| |\n> > -| * | octopus-a\n> > -|/ /\n> > -| * reach\n> > +| | |/\n> > +| * / octopus-a\n> > +| |/\n> > +* / seventh\n> > |/\n> > * Merge branch 'tangle'\n> > |\\\n> > @@ -673,7 +672,7 @@ cat > expect <<\\EOF\n> > * initial\n> > EOF\n> >\n> > -test_expect_success 'log --graph with merge' '\n> > +test_expect_success 'log --graph with merge tag reach' '\n> > git log --graph --date-order --pretty=tformat:%s |\n> > sed \"s/ *\\$//\" >actual &&\n> > test_cmp expect actual\n> > diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh\n> > index 18709a723e..91630c0cae 100755\n> > --- a/t/t4215-log-skewed-merges.sh\n> > +++ b/t/t4215-log-skewed-merges.sh\n> > @@ -5,7 +5,7 @@ test_description='git log --graph of skewed merges'\n> > . ./test-lib.sh\n> >\n> > check_graph () {\n> > - cat >expect &&\n> > + sed \"s/ *$//\" >expect &&\n> > git log --graph --pretty=tformat:%s \"$@\" >actual.raw &&\n> > sed \"s/ *$//\" actual.raw >actual &&\n> > test_cmp expect actual\n> > @@ -185,20 +185,21 @@ test_expect_success 'log --graph with right-skewed merge following a left-skewed\n> >\n> > check_graph --date-order <<-\\EOF\n> > * 4_H\n> > - |\\\n> > + |\\\n> > | * 4_G\n> > - | |\\\n> > + | |\\\n> > + | | * 4_C\n> > | * | 4_F\n> > - |/| |\n> > + |/| |\n> > | * | 4_E\n> > - | |\\ \\\n> > - | | * | 4_D\n> > - | |/ /\n> > - |/| |\n> > - | | * 4_C\n> > - | |/\n> > + | |\\ \\\n> > + | | |/\n> > + | |/|\n> > + | | * 4_D\n> > + | |/\n> > + |/|\n> > | * 4_B\n> > - |/\n> > + |/\n> > * 4_A\n> > EOF\n> > '\n> > @@ -221,21 +222,20 @@ test_expect_success 'log --graph with octopus merge with column joining its penu\n> >\n> > check_graph <<-\\EOF\n> > * 5_H\n> > - |\\\n> > + |\\\n> > | *-. 5_G\n> > - | |\\ \\\n> > + | |\\ \\\n> > | | | * 5_F\n> > | | * | 5_E\n> > - | |/|\\ \\\n> > - | |_|/ /\n> > - |/| | /\n> > - | | |/\n> > - * | | 5_D\n> > + | |/|\\ \\\n> > + | |_|/ /\n> > + |/| | /\n> > + | | |/\n> > | | * 5_C\n> > - | |/\n> > - |/|\n> > - | * 5_B\n> > - |/\n> > + | * | 5_B\n> > + | |/\n> > + * / 5_D\n> > + |/\n> > * 5_A\n> > EOF\n> > '\n> > diff --git a/t/t6003-rev-list-topo-order.sh b/t/t6003-rev-list-topo-order.sh\n> > index 24d1836f41..19cb79bc29 100755\n> > --- a/t/t6003-rev-list-topo-order.sh\n> > +++ b/t/t6003-rev-list-topo-order.sh\n> > @@ -87,12 +87,12 @@ c3\n> > c2\n> > c1\n> > b4\n> > -a3\n> > -a2\n> > -a1\n> > b3\n> > b2\n> > b1\n> > +a3\n> > +a2\n> > +a1\n> > a0\n> > l2\n> > l1\n> > @@ -105,15 +105,15 @@ l5\n> > l4\n> > l3\n> > a4\n> > -b4\n> > -a3\n> > -a2\n> > c3\n> > c2\n> > +c1\n> > +b4\n> > b3\n> > b2\n> > -c1\n> > b1\n> > +a3\n> > +a2\n> > a1\n> > a0\n> > l2\n> > @@ -127,12 +127,12 @@ l5\n> > l4\n> > l3\n> > a4\n> > -b4\n> > c3\n> > c2\n> > +c1\n> > +b4\n> > b3\n> > b2\n> > -c1\n> > b1\n> > a3\n> > a2\n> > @@ -205,12 +205,12 @@ c3\n> > c2\n> > c1\n> > b4\n> > -a3\n> > -a2\n> > -a1\n> > b3\n> > b2\n> > b1\n> > +a3\n> > +a2\n> > +a1\n> > a0\n> > l2\n> > EOF\n> > @@ -224,12 +224,12 @@ c3\n> > c2\n> > c1\n> > b4\n> > -a3\n> > -a2\n> > -a1\n> > b3\n> > b2\n> > b1\n> > +a3\n> > +a2\n> > +a1\n> > a0\n> > l2\n> > EOF\n> > @@ -237,10 +237,10 @@ EOF\n> > test_output_expect_success 'prune near topo' 'git rev-list --topo-order a4 ^c3' < > a4\n> > b4\n> > +b3\n> > a3\n> > a2\n> > a1\n> > -b3\n> > EOF\n> >\n> > test_output_expect_success \"head has no parent\" 'git rev-list --topo-order root' < > @@ -297,8 +297,8 @@ c3\n> > c2\n> > c1\n> > b4\n> > -a3\n> > -a2\n> > +b3\n> > +b2\n> > EOF\n> >\n> > test_output_expect_success \"max-count 10 - non topo order\" 'git rev-list --max-count=10 l5' < > @@ -376,12 +376,12 @@ c3\n> > c2\n> > c1\n> > b4\n> > -a3\n> > -a2\n> > -a1\n> > b3\n> > b2\n> > b1\n> > +a3\n> > +a2\n> > +a1\n> > a0\n> > l2\n> > l1\n> > @@ -399,12 +399,12 @@ c3\n> > c2\n> > c1\n> > b4\n> > -a3\n> > -a2\n> > -a1\n> > b3\n> > b2\n> > b1\n> > +a3\n> > +a2\n> > +a1\n> > a0\n> > l2\n> > l1\n> > @@ -428,12 +428,12 @@ c3\n> > c2\n> > c1\n> > b4\n> > -a3\n> > -a2\n> > -a1\n> > b3\n> > b2\n> > b1\n> > +a3\n> > +a2\n> > +a1\n> > a0\n> > l2\n> > l1\n> > diff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh\n> > index a10f0df02b..9f687b6b22 100755\n> > --- a/t/t6012-rev-list-simplify.sh\n> > +++ b/t/t6012-rev-list-simplify.sh\n> > @@ -122,16 +122,16 @@ check_result () {\n> >\n> > check_result 'L K J I H F E D C G B A' --full-history --topo-order\n> > check_result 'L K I H G F E D C B J A' --full-history\n> > -check_result 'L K I H G F E D C B J A' --full-history --date-order\n> > -check_result 'L K I H G F E D B C J A' --full-history --author-date-order\n> > +check_result 'L K J I H F E D C G B A' --full-history --date-order\n> > +check_result 'L K J I H F E D C G B A' --full-history --author-date-order\n> > check_result 'K I H E C B A' --full-history -- file\n> > check_result 'K I H E C B A' --full-history --topo-order -- file\n> > check_result 'K I H E C B A' --full-history --date-order -- file\n> > -check_result 'K I H E B C A' --full-history --author-date-order -- file\n> > +check_result 'K I H E C B A' --full-history --author-date-order -- file\n> > check_result 'I E C B A' --simplify-merges -- file\n> > check_result 'I E C B A' --simplify-merges --topo-order -- file\n> > check_result 'I E C B A' --simplify-merges --date-order -- file\n> > -check_result 'I E B C A' --simplify-merges --author-date-order -- file\n> > +check_result 'I E C B A' --simplify-merges --author-date-order -- file\n> > check_result 'I B A' -- file\n> > check_result 'I B A' --topo-order -- file\n> > check_result 'I B A' --date-order -- file\n> > diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh\n> > index f5e6e92f5b..5750c6f0fd 100755\n> > --- a/t/t6016-rev-list-graph-simplify-history.sh\n> > +++ b/t/t6016-rev-list-graph-simplify-history.sh\n> > @@ -235,27 +235,28 @@ test_expect_success '--graph ^C3' '\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> > +test_expect_success '--graph --boundary --all ^C3' '\n> > rm -f expected &&\n> > - echo \"* $A7\" >> expected &&\n> > - echo \"* $A6\" >> expected &&\n> > - echo \"|\\\\ \" >> expected &&\n> > - echo \"| * $C4\" >> expected &&\n> > - echo \"* | $A5\" >> expected &&\n> > - echo \"| | \" >> expected &&\n> > - echo \"| \\\\ \" >> expected &&\n> > - echo \"*-. \\\\ $A4\" >> expected &&\n> > - echo \"|\\\\ \\\\ \\\\ \" >> expected &&\n> > - echo \"| * | | $B2\" >> expected &&\n> > - echo \"| * | | $B1\" >> expected &&\n> > - echo \"* | | | $A3\" >> expected &&\n> > - echo \"o | | | $A2\" >> expected &&\n> > - echo \"|/ / / \" >> expected &&\n> > - echo \"o / / $A1\" >> expected &&\n> > - echo \" / / \" >> expected &&\n> > - echo \"| o $C3\" >> expected &&\n> > - echo \"|/ \" >> expected &&\n> > - echo \"o $C2\" >> expected &&\n> > + cat >> expected <<-TESTDATA &&\n> > + * $A7\n> > + * $A6\n> > + |\\\n> > + | * $C4\n> > + * | $A5\n> > + | |\n> > + | \\\n> > + *-. \\ $A4\n> > + |\\ \\ \\\n> > + | * | | $B2\n> > + | * | | $B1\n> > + * | | | $A3\n> > + | | | o $C3\n> > + | | |/\n> > + | | o $C2\n> > + o | $A2\n> > + |/\n> > + o $A1\n> > + TESTDATA\n> > git rev-list --graph --boundary --all ^C3 > actual &&\n> > test_cmp expected actual\n> > '\n> > diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\n> > index b24d850036..a6d389c4fd 100755\n> > --- a/t/t6600-test-reach.sh\n> > +++ b/t/t6600-test-reach.sh\n> > @@ -339,6 +339,8 @@ test_expect_success 'rev-list: ancestry-path topo-order' '\n> > run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6\n> > '\n> >\n> > +# TODO get rid of the \"sort\" below\n> > +# if commitGraph is enabled then sort_in_topological_order is not envoked\n> > test_expect_success 'rev-list: symmetric difference topo-order' '\n> > git rev-parse \\\n> > commit-6-6 commit-5-6 commit-4-6 \\\n> > @@ -349,8 +351,8 @@ test_expect_success 'rev-list: symmetric difference topo-order' '\n> > commit-6-1 commit-5-1 commit-4-1 \\\n> > commit-3-8 commit-2-8 commit-1-8 \\\n> > commit-3-7 commit-2-7 commit-1-7 \\\n> > - >expect &&\n> > - run_three_modes git rev-list --topo-order commit-3-8...commit-6-6\n> > + | sort >expect &&\n> > + run_three_modes git rev-list --topo-order commit-3-8...commit-6-6 | sort\n> > '\n> >\n> > test_expect_success 'get_reachable_subset:all' '\n> > --\n> > gitgitgadget\n> >\n> >\n"},{"id":"389471","messageId":"fa570dcf-b19b-f658-456e-b4174d767ba1@gmail.com","threadId":"52579","inReplyTo":"nycvar.QRO.7.76.6.2001071308290.46@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 0/1] Preserve topological ordering after merges","fromName":"Sergey Rudyshin","fromEmail":"540555@gmail.com","sentAt":"2020-01-08T12:50:42Z","receivedAt":"2020-01-08T12:50:47Z","isPatch":true,"sender":{"key":"540555@gmail.com","avatar":null},"body":"Hi Johannes,\nthanks for you comments!\nplease find my replies below\n\n\n07.01.2020 15:11, Johannes Schindelin wrote:\n> Hi Sergey,\n> \n> On Tue, 7 Jan 2020, Sergey Rudyshin via GitGitGadget wrote:\n> \n>> This modifies the algoritm of topopological ordering. The problem with the\n>> current algoritm is that it displays the graph below as following\n>>\n>> * E\n>> |\\\n>> | * D\n>> | |\\\n>> | |/\n>> |/|\n>> * | C\n>> | * B\n>> |/\n>> * A\n>>\n>> commit B is placed between A and C, which is wrong because E stays that D\n>> and B comes after C\n>>\n>> the only correct solution here is\n>>\n>> * E\n>> |\\\n>> | * D\n>> | |\\\n>> | |/\n>> |/|\n>> | * B\n>> * | C\n>> |/\n>> * A\n>>\n>> while it seems that it contradicts to D staiting that C shoud be between D\n>> and B The new algorithm solves this issue\n>>\n>> Here is an example: walk to to the root via \"first\" parents go E -> C -> A\n>> print A because it has no parents step back to C print C because it has no\n>> other parents then step back to E go D -> B -> A do not print A becase A is\n>> already printed step back to B print B so on\n>>\n>> This change makes option \"--topo-order\" obsolete, because for a single\n>> commit there is only one way to order parents. \"--date-order\" and\n>> \"--author-date-order\" are preserved and make sence only for the case when\n>> multiple commits are given to be able to sort those commits.\n> \n> I have to admit that I am not a fan of this change, as I find that there\n> are legitimate use cases where I want to order the commits by commit\n> topology, and other use cases where I want to order them by date.\n> \n> Maybe other reviewers agree with your reasoning, though, in that case you\n> still will need to address the test failures in t4202, t4215 and t6012:\n> https://dev.azure.com/gitgitgadget/git/_build/results?buildId=25867&view=ms.vss-test-web.build-test-results-tab\n> \n> Ciao,\n> Johannes\n\nlet me explain in more detail why I thought it would make sense to stop \nusing \"--topo-order\".\nin case if a user specifies a single commit, like this\ngit rev-list E\nwith a new algorithm the options \"--date-order\", \"--author-date-order\", \n\"--topo-order\" do not change the ordering. Because there is only one way \nto sort any git graph with a single tip.\n\nin case if a user specifies multiple tips, like this\ngit rev-list --topo-order C B ^A\ncurrent version of git displays commits ordered by commit timestamp\nwhich does not seem like a topological ordering.\n\nso I decided to change the documentation so that \"--topo-order\" and \n\"--date-order\" be the same. And since \"--topo-order\" does not add \nanything new decided to deprecate it.\n\nForm my point of view there should be no options to sort at all.\nThe topology should be derived from the order provided by the user\ngit rev-list --topo-order C B ^A\nshould result in C, B\ngit rev-list --topo-order B C ^A\nshould result in B, C\n\nRegarding the failed test\nI'll try to find the reason but what puzzles me is why those tests \n(t4202, t4215 and t6012) succeeded on all other platforms (linux32, \nosx-clang, windows, ...) and only failed on linux-gcc.\nIn my machine those tests do not fail either (gcc (Ubuntu \n5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609)\n\n"},{"id":"389473","messageId":"222602fc-68a9-0671-e6b9-1aa727d830ea@gmail.com","threadId":"52579","inReplyTo":"fa570dcf-b19b-f658-456e-b4174d767ba1@gmail.com","subject":"Re: [PATCH 0/1] Preserve topological ordering after merges","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-01-08T13:37:00Z","receivedAt":"2020-01-08T13:37:03Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/8/2020 7:50 AM, Sergey Rudyshin wrote:\n> let me explain in more detail why I thought it would make sense to stop using \"--topo-order\".\n> in case if a user specifies a single commit, like this\n> git rev-list E\n> with a new algorithm the options \"--date-order\", \"--author-date-order\", \"--topo-order\" do not change the ordering. Because there is only one way to sort any git graph with a single tip.\n\nThis is false, unless your history is always linear (no merge commits).\n\n> in case if a user specifies multiple tips, like this\n> git rev-list --topo-order C B ^A\n> current version of git displays commits ordered by commit timestamp\n> which does not seem like a topological ordering.\n\nAre you talking about which of C and B are shown first? They are shown in an order based on your input. If C and B are independent (neither can reach the other), then they will swap order if you write \"git rev-list --topo-order B C ^A\".\n\n> so I decided to change the documentation so that \"--topo-order\" and \"--date-order\" be the same. And since \"--topo-order\" does not add anything new decided to deprecate it.\n\nBased on this sentence, it is clear that you do not understand the difference between --topo-order and --date-order. Please take time to examine the output difference for the Git repo with the following commands:\n\n\tgit log --oneline --graph --topo-order\n\tgit log --oneline --graph --date-order\n\n> Regarding the failed test\n> I'll try to find the reason but what puzzles me is why those tests (t4202, t4215 and t6012) succeeded on all other platforms (linux32, osx-clang, windows, ...) and only failed on linux-gcc.\n> In my machine those tests do not fail either (gcc (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609)\n\nTry running the tests with GIT_TEST_COMMIT_GRAPH=1.\n\n-Stolee\n \n\n"},{"id":"389479","messageId":"db0c60f3-a61d-51d3-1e29-0227365e7850@gmail.com","threadId":"52579","inReplyTo":"6c86f1e9-b70b-10b1-f2c5-589312f73a4c@gmail.com","subject":"Re: [PATCH 1/1] Preserve topological ordering after merges This modifies the algorithm of topopological ordering. The problem with the current algoritm is that it displays the graph below as follows","fromName":"Sergey Rudyshin","fromEmail":"540555@gmail.com","sentAt":"2020-01-08T15:11:05Z","receivedAt":"2020-01-08T15:11:16Z","isPatch":true,"sender":{"key":"540555@gmail.com","avatar":null},"body":"Hi Derrick,\nthank you for you feedback!\n\n07.01.2020 15:14, Derrick Stolee wrote:\n> On 1/7/2020 5:30 AM, Sergey Rudyshin via GitGitGadget wrote:\n>> From: Sergey Rudyshin <540555@gmail.com>\n>>\n>> * E\n>> |\\\n>> | * D\n>> | |\\\n>> | |/\n>> |/|\n>> * | C\n>> | * B\n>> |/\n>> * A\n>>\n>> commit B is placed between A and C, which is wrong\n>> because E stays that D and B comes after C\n>>\n>> the only correct solution here is\n>>\n>> * E\n>> |\\\n>> | * D\n>> | |\\\n>> | |/\n>> |/|\n>> | * B\n>> * | C\n>> |/\n>> * A\n>>\n>> while it seems that it contradicts to\n>> D stating that C should be between D and B\n>> The new algorithm solves this issue\n> \n> This ordering concern makes sense _somewhat_, because D is the\n> second parent of D and that wants to say \"Show everything in C..D\n> before showing C\". The issues is that since C is the second parent\n> of D, the topo-ordering says \"Show everything in B..C before showing\n> things reachable from B\". It is unfortunate that these constraints\n> collide.\n> > Perhaps your description could do a better job clarifying this\n> issue and how your algorithm change fixes the problem.\n> \n\nThe proposed algorithm allows to solve collisions you mentioned by \nsticking to the rule which can be summarized as \"new commits do not \nchange history\".\nAnd with that rule in mind choosing between C and B becomes obvious. C \ncomes before B because there was a moment in the history when C existed \nand B did not.\n\nLet's imagine the following scenario.\nSome person maintains some branch.\nAt some point in time the branch contains only two commits A and C.\n\"git rev-list --topo-order\" produces \"A,C\"\nthen the maintainer merges some branch and\n\"git rev-list --topo-order\" starts to produces \"A,B,C,...\"\nwhich is confusing.\n\nThe algorithm itself is similar to the wall follower used in maze solving.\nIf you imagine git graph like a maze where edges corresponds to \ncorridors and nodes to junctions then using \"right-hand rule\" you would \ntraverse the maze. When leaving a junctions if all corridors are visited \n assigning the next number to the junctions you are effectively \nordering them.\n\nLet me repeat the example from my first letter\n* walk to to the root via \"first\" parents;\n* go E -> C -> A;\n* print A because it has no parents;\n* step back to C;\n* print C because it has no other parents;\n* then step back to E;\n* go D -> B -> A;\n* do not print A because A is already printed;\n* step back to B;\n* print B;\n* so on.\n\n\n> However, I'm not sure we even want to make the change, as this\n> is still a valid topological order (parents appear after children).\n> When we have an ambiguous pair (like B and C) the order can differ.\n> The --topo-order option tries to group commits by when they were\n> introduced, and that's the reason for presenting the commits reachable\n> from the later parents before presenting the commits from earlier\n> parents.\n> \n> The only documentation we have is from [1]:\n> \n> \"Show no parents before all of its children are shown, and avoid\n> showing commits on multiple lines of history intermixed.\"\n> \n> The first part of the sentence is still true, and the second part\n> is ambiguous of how to do that.\n> \n> [1] https://git-scm.com/docs/git-log#Documentation/git-log.txt---topo-order\n> \n\nAgreed that it is a a valid topological order but rather for a directed \nacyclic graph. Git has an additional property: edges (parents) are \nordered. Which makes only one way to order it. Ignoring information that \nparents were ordered we had to invent three similar orderings, one of \nthem was ambiguous. For some reason two options do not \"avoid showing \ncommits on multiple lines of history intermixed\". A little confusing.\n\nI think we have an opportunity here to remove options for sorting \neventually thus simplifying leaning curve for users and give them some \nnew features.\n\nLet me step aside and tell why I am proposing this patch in the first \nplace. I am a database developer. And me and my team, we have so called \n\"migrations\": a set of scripts which are to be applied to a database. \nThose scripts are to have a numbers in its filenames so that a tool \ncould install them in a particular order (here is example \nhttps://flywaydb.org/getstarted/how). In our scenario multiple \ndevelopers create those scripts on theirs branches. Those branches get \nmerged into a single integration branch. If Git could preserve commit \nordering after merges it would be possible to generate those filenames \nautomatically. Now it can't. So here am i.\n\n\n>> This change makes option \"--topo-order\" obsolete, because\n>> there is only one way to order parents of a single commit.\n>> \"--date-order\" and \"--author-date-order\" are preserved and make sense\n>> only for the case when multiple commits are given\n>> to be able to sort those commits.\n> \n> This part of the change needs to be removed. The default sort does\n> not preserve topological orderings (like --date-order does), and\n> so is much faster to output, especially without a commit-graph file.\n> \n\nYes indeed. Will fix it.\n\n>> void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order)\n> \n> Since you are only editing this code, and not the incremental topo-order code, your\n> test changes will likely break when run with GIT_TEST_COMMIT_GRAPH=1. When the commit-graph\n> exists and generation numbers are calculated, we use a different algorithm for topo-order.\n> \n\nYes this needs to be reconciled. But unfortunately have no experience in \nthe code for commit graph.\n\n> I've been meaning to clean up this \"duplicated\" logic by deleting this method in favor of\n> the incremental algorithm in all cases. It needs some perf testing to make sure that\n> refactor doesn't have too large of a perf hit in the case of no commit-graph.\n>\nGiven that the new algorithm is pretty simple we could duplicate it \nthere once again.\n\n>> \t/* update the indegree */\n>> @@ -832,51 +886,56 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n>> \tfor (next = orig; next; next = next->next) {\n>> \t\tstruct commit *commit = next->item;\n>> \n>> -\t\tif (*(indegree_slab_at(&indegree, commit)) == 1)\n>> -\t\t\tprio_queue_put(&queue, commit);\n>> +\t\tif (*(indegree_slab_at(&indegree, commit)) == 1) {\n>> +\t\t\t/* also record the author dates, if needed */\n>> +\t\t\tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\n>> +\t\t\t\trecord_author_date(&author_date, commit);\n>> +\t\t\tprio_queue_put(&queue_tips, commit);\n>> +\t\t}\n> \n> Your code change looks rather large for what I expected to be a much simpler change.\n> Likely the only thing we need is to avoid adding to the priority queue if we already\n> have the commit in the queue (maybe using a hashset storing the commits that we've\n> added to the queue). I believe the reason C appears before B in your example is that\n> it was added to the queue a second time, and the queue behaves like a stack in the\n> topo-order case.\n> \nProbably the new code itself could be simplified a bit.\nThanks for suggestion I'll try to think this way.\n\n> Thanks,\n> -Stolee\n> \n"},{"id":"389485","messageId":"077aeb22-ad9c-a9c4-9ee5-21405f85cade@gmail.com","threadId":"52579","inReplyTo":"222602fc-68a9-0671-e6b9-1aa727d830ea@gmail.com","subject":"Re: [PATCH 0/1] Preserve topological ordering after merges","fromName":"Sergey Rudyshin","fromEmail":"540555@gmail.com","sentAt":"2020-01-08T17:04:39Z","receivedAt":"2020-01-08T17:04:50Z","isPatch":true,"sender":{"key":"540555@gmail.com","avatar":null},"body":"Hi Derrick,\n\nThank you for your comments!\n\n08.01.2020 16:37, Derrick Stolee wrote:\n> On 1/8/2020 7:50 AM, Sergey Rudyshin wrote:\n>> let me explain in more detail why I thought it would make sense to stop using \"--topo-order\".\n>> in case if a user specifies a single commit, like this\n>> git rev-list E\n>> with a new algorithm the options \"--date-order\", \"--author-date-order\", \"--topo-order\" do not change the ordering. Because there is only one way to sort any git graph with a single tip.\n> \n> This is false, unless your history is always linear (no merge commits).\n\nWould it be possible to provide some test script which would prove you \npoint? We could run it against the binary created based from \nhttps://github.com/gitgitgadget/git/pull/514/commits/542a02020c8578d0e004cb9c929bced8719b902a\n\n\n> \n>> in case if a user specifies multiple tips, like this\n>> git rev-list --topo-order C B ^A\n>> current version of git displays commits ordered by commit timestamp\n>> which does not seem like a topological ordering.\n> \n> Are you talking about which of C and B are shown first? They are shown in an order based on your input. If C and B are independent (neither can reach the other), then they will swap order if you write \"git rev-list --topo-order B C ^A\".\n> \n\nPlease find a script showing that commits are always sorted by commit \ntimestamp no matter how they appear in the input.\n\n$ cat ./test.sh\n#!/bin/bash\nexport LANGUAGE=en\nGIT=/usr/bin/git\n$GIT --version\nrm -rf .git\n$GIT init\nexport GIT_COMMITTER_DATE=\"2000-01-01T00:00:00 +0000\"\n$GIT commit -m \"0\" --allow-empty\n$GIT tag 0\nexport GIT_COMMITTER_DATE=\"2001-01-01T00:00:00 +0000\"\n$GIT checkout --orphan b1\n$GIT commit -m \"1\" --allow-empty\n$GIT tag 1\nexport GIT_COMMITTER_DATE=\"2002-01-01T00:00:00 +0000\"\n$GIT checkout --orphan b2\n$GIT commit -m \"2\" --allow-empty\n$GIT tag 2\n\nfnc () {\n\techo \"$@\"\n\t$GIT log --graph --pretty=tformat:\"%D %ci\" \"$@\" | sed 's/-01-01 \n00:00:00 +0000//'\n}\nfnc --topo-order 0 1\nfnc --topo-order 1 0\n\nfnc --date-order 0 1\nfnc --date-order 1 0\n\nfnc --topo-order 1 2\nfnc --topo-order 2 1\n\nfnc --date-order 1 2\nfnc --date-order 2 1\n\nfnc --topo-order 0 1 2\nfnc --topo-order 2 1 0\n\n$ ./test.sh\ngit version 2.7.4\nInitialized empty Git repository in /tmp/git_test_case_ordering/.git/\n[master (root-commit) 0a449fc] 0\nSwitched to a new branch 'b1'\n[b1 (root-commit) 070d07f] 1\nSwitched to a new branch 'b2'\n[b2 (root-commit) c751327] 2\n--topo-order 0 1\n* tag: 1, b1 2001\n* tag: 0, master 2000\n--topo-order 1 0\n* tag: 1, b1 2001\n* tag: 0, master 2000\n--date-order 0 1\n* tag: 1, b1 2001\n* tag: 0, master 2000\n--date-order 1 0\n* tag: 1, b1 2001\n* tag: 0, master 2000\n--topo-order 1 2\n* HEAD -> b2, tag: 2 2002\n* tag: 1, b1 2001\n--topo-order 2 1\n* HEAD -> b2, tag: 2 2002\n* tag: 1, b1 2001\n--date-order 1 2\n* HEAD -> b2, tag: 2 2002\n* tag: 1, b1 2001\n--date-order 2 1\n* HEAD -> b2, tag: 2 2002\n* tag: 1, b1 2001\n--topo-order 0 1 2\n* HEAD -> b2, tag: 2 2002\n* tag: 1, b1 2001\n* tag: 0, master 2000\n--topo-order 2 1 0\n* HEAD -> b2, tag: 2 2002\n* tag: 1, b1 2001\n* tag: 0, master 2000\n\n\n\n>> so I decided to change the documentation so that \"--topo-order\" and \"--date-order\" be the same. And since \"--topo-order\" does not add anything new decided to deprecate it.\n> \n> Based on this sentence, it is clear that you do not understand the difference between --topo-order and --date-order. Please take time to examine the output difference for the Git repo with the following commands:\n> \n> \tgit log --oneline --graph --topo-order\n> \tgit log --oneline --graph --date-order\n> \n\nHope that the script above will clarify what i meant.\n\n>> Regarding the failed test\n>> I'll try to find the reason but what puzzles me is why those tests (t4202, t4215 and t6012) succeeded on all other platforms (linux32, osx-clang, windows, ...) and only failed on linux-gcc.\n>> In my machine those tests do not fail either (gcc (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609)\n> \n> Try running the tests with GIT_TEST_COMMIT_GRAPH=1.\n> \n\nYes it helped. With that option the tests starts to fail.\nI'll try to find out how COMMIT_GRAPH works and fix it.\n\n> -Stolee\n> \n> \n\nPS\nexcluded Junio from the loop per his request.\n"}]}