{"thread":{"id":"50629","subject":"[PATCH 1/1] Add feature to show log as a tree","startedAt":"2019-03-03T10:37:58Z","lastAt":"2019-03-04T09:13:29Z","messageCount":3,"participants":["Micha Nelissen","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"370508","messageId":"20190303103751.6523-1-nelissen.micha@gmail.com","threadId":"50629","inReplyTo":null,"subject":"[PATCH 1/1] Add feature to show log as a tree","fromName":"Micha Nelissen","fromEmail":"nelissen.micha@gmail.com","sentAt":"2019-03-03T10:37:51Z","receivedAt":"2019-03-03T10:37:58Z","isPatch":true,"sender":{"key":"nelissen.micha@gmail.com","avatar":null},"body":"Modifies the topo-order code to keep track of the first child,\nusing a heuristic. The heuristic works by assigning a (depth)\nlevel to all nodes. The first child is the node of which this\nnode is a parent of and has the lowest level. Then it cuts all\nthe links that are not the first child, resulting in a tree.\n\nIt also uses the level to sort the nodes: trying to keep\ndescendent line (of a merge) together as a group.\n\nAdd commandline option \"--tree\" to use this new feature.\n\nSigned-off-by: Micha Nelissen <nelissen.micha@gmail.com>\n---\n commit.c   | 136 +++++++++++++++++++++++++++++++++++++++++++++++------\n commit.h   |   1 +\n revision.c |   4 ++\n 3 files changed, 127 insertions(+), 14 deletions(-)\n\ndiff --git commit.c commit.c\nindex a5333c7ac6..340757adc2 100644\n--- commit.c\n+++ commit.c\n@@ -662,7 +662,12 @@ struct commit *pop_commit(struct commit_list **stack)\n  */\n \n /* count number of children that have not been emitted */\n-define_commit_slab(indegree_slab, int);\n+struct indegree {\n+\tunsigned short indegree;\n+\tunsigned short level;\t  /* first level this commit has been seen at */\n+};\n+define_commit_slab(indegree_slab, struct indegree);\n+define_commit_slab(first_child_slab, struct commit *);\n \n define_commit_slab(author_date_slab, timestamp_t);\n \n@@ -708,6 +713,22 @@ int compare_commits_by_author_date(const void *a_, const void *b_,\n \treturn 0;\n }\n \n+static int compare_commits_by_tree_level(const void *a_, const void *b_,\n+\t\t\t\t\t void *cb_data)\n+{\n+\tconst struct commit *a = a_, *b = b_;\n+\tstruct indegree_slab *indegree = cb_data;\n+\tunsigned short a_level = indegree_slab_at(indegree, a)->level;\n+\tunsigned short b_level = indegree_slab_at(indegree, b)->level;\n+\n+\t/* deepest tree level commits first */\n+\tif (a_level < b_level)\n+\t\treturn 1;\n+\telse if (a_level > b_level)\n+\t\treturn -1;\n+\treturn 0;\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@@ -745,6 +766,7 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \tstruct commit_list *next, *orig = *list;\n \tstruct commit_list **pptr;\n \tstruct indegree_slab indegree;\n+\tstruct first_child_slab first_child;\n \tstruct prio_queue queue;\n \tstruct commit *commit;\n \tstruct author_date_slab author_date;\n@@ -760,6 +782,11 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n \t\tqueue.compare = NULL;\n \t\tbreak;\n+\tcase REV_SORT_IN_TREE_ORDER:\n+\t\tinit_first_child_slab(&first_child);\n+\t\tqueue.compare = compare_commits_by_tree_level;\n+\t\tqueue.cb_data = &indegree;\n+\t\tbreak;\n \tcase REV_SORT_BY_COMMIT_DATE:\n \t\tqueue.compare = compare_commits_by_commit_date;\n \t\tbreak;\n@@ -773,7 +800,8 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \t/* Mark them and clear the indegree */\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\tstruct indegree *pi = indegree_slab_at(&indegree, commit);\n+\t\tpi->indegree = 0, pi->level = 0;\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@@ -782,13 +810,12 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \t/* update the indegree */\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit_list *parents = next->item->parents;\n-\t\twhile (parents) {\n+\t\tfor (; 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-\t\t\t\t(*pi)++;\n-\t\t\tparents = parents->next;\n+\t\t\tstruct indegree *pi = indegree_slab_peek(&indegree, parent);\n+\t\t\tif (!pi)\n+\t\t\t\tcontinue;\n+\t\t\tpi->indegree++;\n \t\t}\n \t}\n \n@@ -801,9 +828,12 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \t */\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n+\t\tstruct indegree *pi = indegree_slab_at(&indegree, commit);\n \n-\t\tif (*(indegree_slab_at(&indegree, commit)) == 1)\n+\t\tif (pi->indegree == 0) {\n+\t\t\tpi->level = 1;\n \t\t\tprio_queue_put(&queue, commit);\n+\t\t}\n \t}\n \n \t/*\n@@ -820,31 +850,109 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \t*list = NULL;\n \twhile ((commit = prio_queue_get(&queue)) != NULL) {\n \t\tstruct commit_list *parents;\n+\t\tunsigned short commit_level, parent_level;\n+\t\tcommit_level = parent_level = indegree_slab_at(&indegree, commit)->level;\n \n-\t\tfor (parents = commit->parents; parents ; parents = parents->next) {\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+\t\t\tstruct indegree *pi = indegree_slab_peek(&indegree, parent);\n \n-\t\t\tif (!*pi)\n+\t\t\tif (!pi)\n \t\t\t\tcontinue;\n \n+\t\t\tif (sort_order == REV_SORT_IN_TREE_ORDER) {\n+\t\t\t\tstruct commit **pfirst_child =\n+\t\t\t\t\tfirst_child_slab_at(&first_child, parent);\n+\t\t\t\tif (*pfirst_child != NULL) {\n+\t\t\t\t\t/* already set a first child, if it is from higher\n+\t\t\t\t\t   level than we are, set ourselves as first */\n+\t\t\t\t\tstruct indegree *old_pi =\n+\t\t\t\t\t\tindegree_slab_at(&indegree, *pfirst_child);\n+\t\t\t\t\tif (old_pi->level >= commit_level)\n+\t\t\t\t\t\t*pfirst_child = NULL;\n+\t\t\t\t}\n+\t\t\t\tif (*pfirst_child == NULL)\n+\t\t\t\t\t*pfirst_child = commit;\n+\n+\t\t\t\tif (!pi->level || parent_level < pi->level) {\n+\t\t\t\t\tstruct commit_list *gparent_list;\n+\t\t\t\t\tstruct commit *gparent = parent;\n+\t\t\t\t\tstruct indegree *gpi;\n+\t\t\t\t\t/* mark this 'branch' as this level */\n+\t\t\t\t\tpi->level = parent_level;\n+\t\t\t\t\twhile ((gparent_list = gparent->parents) != NULL) {\n+\t\t\t\t\t\tgparent = gparent_list->item;\n+\t\t\t\t\t\tgpi = indegree_slab_peek(&indegree, gparent);\n+\t\t\t\t\t\tif (!gpi ||\n+\t\t\t\t\t\t    (gpi->level && gpi->level < parent_level))\n+\t\t\t\t\t\t\tbreak;\n+\t\t\t\t\t\tgpi->level = parent_level;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t\tif (pi->level >= parent_level)\n+\t\t\t\t\tparent_level = pi->level + 1;\n+\t\t\t}\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\tif (--pi->indegree == 0)\n \t\t\t\tprio_queue_put(&queue, parent);\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+\t\tindegree_slab_at(&indegree, commit)->indegree = 0;\n \n \t\tpptr = &commit_list_insert(commit, pptr)->next;\n \t}\n \n+\tif (sort_order == REV_SORT_IN_TREE_ORDER) {\n+\t\tstruct commit *commit, *next_commit;\n+\t\t/*\n+\t\t * go through the commit list to cut all the non-first\n+\t\t * parent-child links, so we get a tree\n+\t\t */\n+\t\tnext = *list;\n+\t\tif (next) {\n+\t\t\tcommit = next->item;\n+\t\t\tnext = next->next;\n+\t\t}\n+\t\tfor (next = *list; next; next = next->next, commit = next_commit) {\n+\t\t\tstruct commit_list *parents, **pparents = &commit->parents;\n+\t\t\tnext_commit = next->item;\n+\t\t\tfor (parents = commit->parents; parents; parents = parents->next) {\n+\t\t\t\t/* leave link between sequential commits alone because\n+\t\t\t\t   the level is not 100% to column mapping. level might\n+\t\t\t\t   be higher due to merges of merges from the same\n+\t\t\t\t   origin; except if the next commit is on top level\n+\t\t\t\t   then for sure it's not the same column */\n+\t\t\t\tstruct commit *parent = parents->item;\n+\t\t\t\tint cut = 1;\n+\t\t\t\tif (parent == next_commit) {\n+\t\t\t\t\tstruct indegree *pi =\n+\t\t\t\t\t\tindegree_slab_peek(&indegree, parent);\n+\t\t\t\t\t/* cut as in, allow to cut */\n+\t\t\t\t\tcut = pi && pi->level == 1;\n+\t\t\t\t}\n+\t\t\t\tif (cut) {\n+\t\t\t\t\tstruct commit **pfirst_child =\n+\t\t\t\t\t\tfirst_child_slab_at(&first_child, parent);\n+\t\t\t\t\tcut = commit != *pfirst_child;\n+\t\t\t\t}\n+\t\t\t\tif (cut)\n+\t\t\t\t\t*pparents = parents->next;\n+\t\t\t\telse\n+\t\t\t\t\tpparents = &parents->next;\n+\t\t\t}\n+\t\t}\n+\n+\t\tclear_first_child_slab(&first_child);\n+\t}\n+\n \tclear_indegree_slab(&indegree);\n \tclear_prio_queue(&queue);\n \tif (sort_order == REV_SORT_BY_AUTHOR_DATE)\ndiff --git commit.h commit.h\nindex 42728c2906..25b236cb49 100644\n--- commit.h\n+++ commit.h\n@@ -205,6 +205,7 @@ void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark);\n \n enum rev_sort_order {\n \tREV_SORT_IN_GRAPH_ORDER = 0,\n+\tREV_SORT_IN_TREE_ORDER,\n \tREV_SORT_BY_COMMIT_DATE,\n \tREV_SORT_BY_AUTHOR_DATE\n };\ndiff --git revision.c revision.c\nindex 162d511d46..09074e2c08 100644\n--- revision.c\n+++ revision.c\n@@ -2031,6 +2031,9 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--topo-order\")) {\n \t\trevs->sort_order = REV_SORT_IN_GRAPH_ORDER;\n \t\trevs->topo_order = 1;\n+\t} else if (!strcmp(arg, \"--tree\")) {\n+\t\trevs->sort_order = REV_SORT_IN_TREE_ORDER;\n+\t\tgoto graph;\n \t} else if (!strcmp(arg, \"--simplify-merges\")) {\n \t\trevs->simplify_merges = 1;\n \t\trevs->topo_order = 1;\n@@ -2227,6 +2230,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\trevs->pretty_given = 1;\n \t\trevs->abbrev_commit = 1;\n \t} else if (!strcmp(arg, \"--graph\")) {\n+\t    graph:\n \t\trevs->topo_order = 1;\n \t\trevs->rewrite_parents = 1;\n \t\trevs->graph = graph_init(revs);\n-- \n2.17.1\n\n"},{"id":"370514","messageId":"xmqqd0n814kg.fsf@gitster-ct.c.googlers.com","threadId":"50629","inReplyTo":"20190303103751.6523-1-nelissen.micha@gmail.com","subject":"Re: [PATCH 1/1] Add feature to show log as a tree","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-03-03T13:16:15Z","receivedAt":"2019-03-03T13:16:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Micha Nelissen <nelissen.micha@gmail.com> writes:\n\n> Modifies the topo-order code to keep track of the first child,\n> using a heuristic. The heuristic works by assigning a (depth)\n> level to all nodes. The first child is the node of which this\n> node is a parent of and has the lowest level. Then it cuts all\n> the links that are not the first child, resulting in a tree.\n\nI am not sure what you mean by a \"tree\".  It definitely is not a\ntree perceived by Git users (which is what represents a directory\nstructure), and abusing the established term is confusing.\n\nThere is no inherent ordering among children of a given commit, so\nyou'd invent some way to define what \"the first child\" is.  That\nmuch can be read from the above, but what is missing is why do you\neven need to bother.  What benefit do users get by identifying \"the\nfirst\" child and cutting all others off---that is the necessary\njustification for this change, which is missing from the above\nexplanation.\n\n\"A (depth) level\" is poorly explained---in fact, it is not explained\nwhat it means at all.  \"We designate the first child of each commit\nby some magic\" is all we can read from it.\n\nPlease try again.\n\nAfter explaining \"some magic\" in a more meaningful way, perhaps\nyou'd realize that you'd want to stop saying \"first child\".  It\nfeels to me that you want to use a heuristic to identify the most\nimportant single line of history leading to the tip.  If that is\nwhat you are doing, then the resulting shape of the history would\nnot be a tree (where branching is an important aspect, and both\nsides of the branches are important) but a linear line (where you\nignore all side branches and concentrate only on the trunk of a\ntree).  And I'd probably call each child that is on the \"trunk\" line\nof the most important lineage \"primary child\" or something like\nthat.\n\n> It also uses the level to sort the nodes: trying to keep\n> descendent line (of a merge) together as a group.\n>\n> Add commandline option \"--tree\" to use this new feature.\n\nIn any case, if this is to sit next to and be friends with\n\"--topo-order\", the option should be named as \"--some-order\".\nThe option name \"--tree\" (or \"--blob\", \"--tag\", or \"--commit\" for\nthat matter) is obviously unacceptable if the option is about\nspecifying how the commits in the \"git log\" output are ordered.\n\nHaving said that, if you are omitting commits that are not on the\nprimary lineage of the history, then this is not \"--anything-order\"\noption, in which case it may want to sit next to and be friends with\n\"--first-parent\", perhaps?  with the fuzzy description and\nexplanation above, I cannot quite guess the answer to this question\nmyself so I'll stop here.\n\n> Signed-off-by: Micha Nelissen <nelissen.micha@gmail.com>\n> ---\n>  commit.c   | 136 +++++++++++++++++++++++++++++++++++++++++++++++------\n>  commit.h   |   1 +\n>  revision.c |   4 ++\n\nWithout clear explanation of what the change attempts to achieve in\ndocs and tests, there is no way to review to see if the new code is\ncorrect.\n"},{"id":"370585","messageId":"cc77a06e-2fa7-f3b3-dcc4-9bf385d7f384@gmail.com","threadId":"50629","inReplyTo":"xmqqd0n814kg.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 1/1] Add feature to show log as a tree","fromName":"Micha Nelissen","fromEmail":"nelissen.micha@gmail.com","sentAt":"2019-03-04T09:13:23Z","receivedAt":"2019-03-04T09:13:29Z","isPatch":true,"sender":{"key":"nelissen.micha@gmail.com","avatar":null},"body":"On 03-03-2019 14:16, Junio C Hamano wrote:\n> I am not sure what you mean by a \"tree\".  It definitely is not a\n> tree perceived by Git users (which is what represents a directory\n> structure), and abusing the established term is confusing.\n\nI called it tree because the output looks like (right half) of a tree. \nI'm open to alternatives though.\n\n> There is no inherent ordering among children of a given commit, so\n> you'd invent some way to define what \"the first child\" is.  That\n> much can be read from the above, but what is missing is why do you\n> even need to bother.  What benefit do users get by identifying \"the\n> first\" child and cutting all others off---that is the necessary\n> justification for this change, which is missing from the above\n> explanation.\n\nRight, in my mind the problem statement is so clear and I didn't write \nit down. There should have been an introduction paragraph.\n\nProblem I want to solve. The --graph output is useful but often \nunreadable, due to the many parallel lines. On the other hand, with the \ndefault straight line log output all structure is lost. I am trying some \nmiddle ground to see merge structure, but keep history readable. I \nnoticed in particular the branch point causes a line to go around or go \nin between many commits leading to clutter, so I want to remove these. \nBy itself the exact point branched from is rarely important (at least to \nme). And if it is, then there still is --graph :-).\n\n> \"A (depth) level\" is poorly explained---in fact, it is not explained\n> what it means at all.  \"We designate the first child of each commit\n> by some magic\" is all we can read from it.\n\nWhen processing the commit nodes. Start with depth level 0. Given some \ncurrent depth level D, assign depth level D, D+1, ... D+N-1 to the N \nparents of a (merge) commit. Recurse.\n\nIn the output, the depth level is more or less the column number the \nstar '*' is in. (Although after merges of merges, there will be gaps in \nthe level numbering.)\n\n> After explaining \"some magic\" in a more meaningful way, perhaps\n> you'd realize that you'd want to stop saying \"first child\".  It\n\nOK well, the term \"first parent\" is already in the man page, right? \n--first-parent. So the first child of a commit is the commit C among all \nchildren H, such that when all of H are traced back to a common point S, \nthe trace line from C is the one that ends being the first parent of S.\n\n> ignore all side branches and concentrate only on the trunk of a\n> tree).  And I'd probably call each child that is on the \"trunk\" line\n> of the most important lineage \"primary child\" or something like\n> that.\n\nSort of, but remember this works recursive, there can be merges of \nmerges. Therefore the output is not a single trunk line. In other words, \nthe above commit S doesn't need to be on the trunk (or, '*' completely \nleft in the graph output).\n\n> In any case, if this is to sit next to and be friends with\n> \"--topo-order\", the option should be named as \"--some-order\".\n> The option name \"--tree\" (or \"--blob\", \"--tag\", or \"--commit\" for\n> that matter) is obviously unacceptable if the option is about\n> specifying how the commits in the \"git log\" output are ordered.\n\nI see it as alternative to the --graph option. I also made it jump \nthere, but maybe gotos are rejected from style point of view. In this \ncase I thought it would be clear to see it as alternative to --graph.\n\nIt doesn't do justice in my opinion to call it --graph --micha-order (or \nwhatever ;-)), as it is not only about changing the order of commit \ndisplay. But again, I'm open to alternatives, I can make a personal \nalias anyway :-).\n\n> Having said that, if you are omitting commits that are not on the\n> primary lineage of the history, then this is not \"--anything-order\"\n> option, in which case it may want to sit next to and be friends with\n\nAh no, it doesn't omit any commits. All commits are displayed.\n\n> Without clear explanation of what the change attempts to achieve in\n> docs and tests, there is no way to review to see if the new code is\n> correct.\n\nHow can I add tests for this feature? I'm also open to what kinds of \ndocumentation to add, as I find it way easier to explain when you \nactually run it to see the output it generates, than from abstract \nparagraph of documentation text (like a manpage has). Some \nmathematical-type of explanation like above is also not really \nimmediately enlightening, and also not necessary to use it I think.\n\nThanks for review, Micha\n\n\n"}]}