{"thread":{"id":"3351","subject":"git-rev-list --date-order ?","startedAt":"2006-02-16T02:40:46Z","lastAt":"2006-02-16T06:18:29Z","messageCount":3,"participants":["Paul Mackerras","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"16236","messageId":"17395.58926.26670.23572@cargo.ozlabs.ibm.com","threadId":"3351","inReplyTo":null,"subject":"git-rev-list --date-order ?","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2006-02-16T02:40:46Z","receivedAt":"2006-02-16T02:40:46Z","isPatch":false,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Junio,\n\nGitk has a -d option that tells it to reorder the commits in\ndecreasing order of their commit time, subject to the constraint that\nparents come after all of their children.  Currently it uses\ngit-rev-list --header --topo-order --parents and then reorders the\ncommits internally.\n\nHow hard would it be to add a --date-order flag to git-rev-list to\nmake it order the commits in decreasing commit time order, subject to\nthe constraint that parents come after their children?\n\nIf we had that then I could remove another chunk of code from gitk and\nmake it a bit faster.\n\nThanks,\nPaul.\n"},{"id":"16237","messageId":"7vpsloknfq.fsf@assigned-by-dhcp.cox.net","threadId":"3351","inReplyTo":"17395.58926.26670.23572@cargo.ozlabs.ibm.com","subject":"Re: git-rev-list --date-order ?","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-16T03:11:21Z","receivedAt":"2006-02-16T03:11:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Paul Mackerras <paulus@samba.org> writes:\n\n> Junio,\n>\n> Gitk has a -d option that tells it to reorder the commits in\n> decreasing order of their commit time, subject to the constraint that\n> parents come after all of their children.  Currently it uses\n> git-rev-list --header --topo-order --parents and then reorders the\n> commits internally.\n>\n> How hard would it be to add a --date-order flag to git-rev-list to\n> make it order the commits in decreasing commit time order, subject to\n> the constraint that parents come after their children?\n>\n> If we had that then I could remove another chunk of code from gitk and\n> make it a bit faster.\n\nIt's been a while that I read the topo-order code, but I suspect\nsomething like this?  I may be completely off the mark here.\n\n--\ndiff --git a/commit.c b/commit.c\nindex 67e11d7..0d94e4d 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -630,7 +630,9 @@ void sort_in_topological_order(struct co\n \t\t}\n \t\tnext=next->next;\n \t}\n+\n \t/* process the list in topological order */\n+\tsort_by_date(&work);\n \twhile (work) {\n \t\tstruct commit * work_item = pop_commit(&work);\n \t\tstruct sort_node * work_node = (struct sort_node *)work_item->object.util;\n@@ -648,7 +650,7 @@ void sort_in_topological_order(struct co\n                                  */\n \t\t\t\tpn->indegree--;\n \t\t\t\tif (!pn->indegree) \n-\t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t\t\tinsert_by_date(parent, &work);\n \t\t\t}\n \t\t\tparents=parents->next;\n \t\t}\n"},{"id":"16245","messageId":"7vbqx7keru.fsf@assigned-by-dhcp.cox.net","threadId":"3351","inReplyTo":"17395.58926.26670.23572@cargo.ozlabs.ibm.com","subject":"[PATCH] topo-order: make --date-order optional.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-16T06:18:29Z","receivedAt":"2006-02-16T06:18:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This adds --date-order to rev-list; it is similar to topo order\nin the sense that no parent comes before all of its children,\nbut otherwise things are still ordered in the commit timestamp\norder.\n\nThe same flag is also added to show-branch.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n * Paul, this supersedes the previous one, which made topo-order\n   behave date-order unconditionally.\n\n   The thing is, topological ordering code has a nice property\n   that the equally eligible ones are pushed into a LIFO, which\n   keeps single strand of pearls together and as good as the\n   merge order for practical purposes.  Doing date-order breaks\n   it.  Since we would want both, there is a new option as you\n   originally wanted.\n\n   I've tested it to see that it passes the tests, but that is\n   not saying much ;-).\n\n commit.c      |   13 ++++++++++---\n commit.h      |    4 +++-\n rev-list.c    |   11 ++++++++++-\n rev-parse.c   |    1 +\n show-branch.c |    9 +++++----\n 5 files changed, 29 insertions(+), 9 deletions(-)\n\n4c8725f16abff4be4812d0d07a663250bef3ef0e\ndiff --git a/commit.c b/commit.c\nindex 67e11d7..c550a00 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -571,7 +571,7 @@ int count_parents(struct commit * commit\n /*\n  * Performs an in-place topological sort on the list supplied.\n  */\n-void sort_in_topological_order(struct commit_list ** list)\n+void sort_in_topological_order(struct commit_list ** list, int lifo)\n {\n \tstruct commit_list * next = *list;\n \tstruct commit_list * work = NULL, **insert;\n@@ -630,7 +630,10 @@ void sort_in_topological_order(struct co\n \t\t}\n \t\tnext=next->next;\n \t}\n+\n \t/* process the list in topological order */\n+\tif (!lifo)\n+\t\tsort_by_date(&work);\n \twhile (work) {\n \t\tstruct commit * work_item = pop_commit(&work);\n \t\tstruct sort_node * work_node = (struct sort_node *)work_item->object.util;\n@@ -647,8 +650,12 @@ void sort_in_topological_order(struct co\n                                  * guaranteeing topological order.\n                                  */\n \t\t\t\tpn->indegree--;\n-\t\t\t\tif (!pn->indegree) \n-\t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t\tif (!pn->indegree) {\n+\t\t\t\t\tif (!lifo)\n+\t\t\t\t\t\tinsert_by_date(parent, &work);\n+\t\t\t\t\telse\n+\t\t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t\t}\n \t\t\t}\n \t\t\tparents=parents->next;\n \t\t}\ndiff --git a/commit.h b/commit.h\nindex 986b22d..70a7c75 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -72,6 +72,8 @@ int count_parents(struct commit * commit\n  * Post-conditions: \n  *   invariant of resulting list is:\n  *      a reachable from b => ord(b) < ord(a)\n+ *   in addition, when lifo == 0, commits on parallel tracks are\n+ *   sorted in the dates order.\n  */\n-void sort_in_topological_order(struct commit_list ** list);\n+void sort_in_topological_order(struct commit_list ** list, int lifo);\n #endif /* COMMIT_H */\ndiff --git a/rev-list.c b/rev-list.c\nindex 63391fc..f2d1105 100644\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -27,6 +27,7 @@ static const char rev_list_usage[] =\n \"  ordering output:\\n\"\n \"    --merge-order [ --show-breaks ]\\n\"\n \"    --topo-order\\n\"\n+\"    --date-order\\n\"\n \"  formatting output:\\n\"\n \"    --parents\\n\"\n \"    --objects\\n\"\n@@ -56,6 +57,7 @@ static int merge_order = 0;\n static int show_breaks = 0;\n static int stop_traversal = 0;\n static int topo_order = 0;\n+static int lifo = 1;\n static int no_merges = 0;\n static const char **paths = NULL;\n static int remove_empty_trees = 0;\n@@ -856,6 +858,13 @@ int main(int argc, const char **argv)\n \t\t}\n \t\tif (!strcmp(arg, \"--topo-order\")) {\n \t\t        topo_order = 1;\n+\t\t\tlifo = 1;\n+\t\t        limited = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"--date-order\")) {\n+\t\t        topo_order = 1;\n+\t\t\tlifo = 0;\n \t\t        limited = 1;\n \t\t\tcontinue;\n \t\t}\n@@ -940,7 +949,7 @@ int main(int argc, const char **argv)\n \t        if (limited)\n \t\t\tlist = limit_list(list);\n \t\tif (topo_order)\n-\t\t\tsort_in_topological_order(&list);\n+\t\t\tsort_in_topological_order(&list, lifo);\n \t\tshow_commit_list(list);\n \t} else {\n #ifndef NO_OPENSSL\ndiff --git a/rev-parse.c b/rev-parse.c\nindex b82f294..9161fae 100644\n--- a/rev-parse.c\n+++ b/rev-parse.c\n@@ -48,6 +48,7 @@ static int is_rev_argument(const char *a\n \t\t\"--show-breaks\",\n \t\t\"--sparse\",\n \t\t\"--topo-order\",\n+\t\t\"--date-order\",\n \t\t\"--unpacked\",\n \t\tNULL\n \t};\ndiff --git a/show-branch.c b/show-branch.c\nindex 511fd3b..5a86ae2 100644\n--- a/show-branch.c\n+++ b/show-branch.c\n@@ -535,6 +535,7 @@ int main(int ac, char **av)\n \tint num_rev, i, extra = 0;\n \tint all_heads = 0, all_tags = 0;\n \tint all_mask, all_revs;\n+\tint lifo = 1;\n \tchar head_path[128];\n \tconst char *head_path_p;\n \tint head_path_len;\n@@ -544,7 +545,6 @@ int main(int ac, char **av)\n \tint no_name = 0;\n \tint sha1_name = 0;\n \tint shown_merge_point = 0;\n-\tint topo_order = 0;\n \tint with_current_branch = 0;\n \tint head_at = -1;\n \n@@ -586,7 +586,9 @@ int main(int ac, char **av)\n \t\telse if (!strcmp(arg, \"--independent\"))\n \t\t\tindependent = 1;\n \t\telse if (!strcmp(arg, \"--topo-order\"))\n-\t\t\ttopo_order = 1;\n+\t\t\tlifo = 1;\n+\t\telse if (!strcmp(arg, \"--date-order\"))\n+\t\t\tlifo = 0;\n \t\telse\n \t\t\tusage(show_branch_usage);\n \t\tac--; av++;\n@@ -710,8 +712,7 @@ int main(int ac, char **av)\n \t\texit(0);\n \n \t/* Sort topologically */\n-\tif (topo_order)\n-\t\tsort_in_topological_order(&seen);\n+\tsort_in_topological_order(&seen, lifo);\n \n \t/* Give names to commits */\n \tif (!sha1_name && !no_name)\n-- \n1.2.1.gbf0a\n"}]}