{"thread":{"id":"50630","subject":"[PATCH] Make graph drawing more compact","startedAt":"2019-03-03T12:00:10Z","lastAt":"2019-03-03T12:00:10Z","messageCount":1,"participants":["Micha Nelissen"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"370509","messageId":"20190303115957.11871-1-nelissen.micha@gmail.com","threadId":"50630","inReplyTo":null,"subject":"[PATCH] Make graph drawing more compact","fromName":"Micha Nelissen","fromEmail":"nelissen.micha@gmail.com","sentAt":"2019-03-03T11:59:57Z","receivedAt":"2019-03-03T12:00:10Z","isPatch":true,"sender":{"key":"nelissen.micha@gmail.com","avatar":null},"body":"Before this commit, graphs with merges have an empty line after a\nmerge commit to make room for a new branch. But this causes the\nchild commits (commits merged with the merge commit) to be separated\nfrom the merge commit. Especially with the --tree option this\nis confusing, as there is no empty line after a series of child\ncommits anymore (because it is a tree after all).\n\nTherefore this change modifies the merge point to not need an\nextra line (the POST_MERGE state is removed), using an underscore\nto branch out instead of a '\\'.\n\nIt also optimizes the case where a branch point meets a merge commit.\n\nSigned-off-by: Micha Nelissen <nelissen.micha@gmail.com>\n---\n graph.c | 281 +++++++++++++++++---------------------------------------\n 1 file changed, 85 insertions(+), 196 deletions(-)\n\ndiff --git graph.c graph.c\nindex f53135485f..f0e30bce62 100644\n--- graph.c\n+++ graph.c\n@@ -63,7 +63,6 @@ enum graph_state {\n \tGRAPH_SKIP,\n \tGRAPH_PRE_COMMIT,\n \tGRAPH_COMMIT,\n-\tGRAPH_POST_MERGE,\n \tGRAPH_COLLAPSING\n };\n \n@@ -153,12 +152,6 @@ struct git_graph {\n \t * This tells us what kind of line graph_next_line() should output.\n \t */\n \tenum graph_state state;\n-\t/*\n-\t * The output state for the previous line of output.\n-\t * This is primarily used to determine how the first merge line\n-\t * should appear, based on the last line of the previous commit.\n-\t */\n-\tenum graph_state prev_state;\n \t/*\n \t * The index of the column that refers to this commit.\n \t *\n@@ -167,13 +160,9 @@ struct git_graph {\n \t */\n \tint commit_index;\n \t/*\n-\t * The commit_index for the previously displayed commit.\n-\t *\n-\t * This is used to determine how the first line of a merge\n-\t * graph output should appear, based on the last line of the\n-\t * previous commit.\n+\t * If previous line was a merge commit, then this is its commit index\n \t */\n-\tint prev_commit_index;\n+\tint prev_merge_index;\n \t/*\n \t * The maximum number of columns that can be stored in the columns\n \t * and new_columns arrays.  This is also half the number of entries\n@@ -282,9 +271,7 @@ struct git_graph *graph_init(struct rev_info *opt)\n \tgraph->num_parents = 0;\n \tgraph->expansion_row = 0;\n \tgraph->state = GRAPH_PADDING;\n-\tgraph->prev_state = GRAPH_PADDING;\n \tgraph->commit_index = 0;\n-\tgraph->prev_commit_index = 0;\n \tgraph->num_columns = 0;\n \tgraph->num_new_columns = 0;\n \tgraph->mapping_size = 0;\n@@ -317,7 +304,6 @@ struct git_graph *graph_init(struct rev_info *opt)\n \n static void graph_update_state(struct git_graph *graph, enum graph_state s)\n {\n-\tgraph->prev_state = graph->state;\n \tgraph->state = s;\n }\n \n@@ -602,6 +588,13 @@ static void graph_update_columns(struct git_graph *graph)\n \tgraph_update_width(graph, is_commit_in_columns);\n }\n \n+static int need_pre_commit(struct git_graph *graph)\n+{\n+\treturn (graph->num_parents == 2 && graph->prev_merge_index != 0xffff)\n+\t    || (graph->num_parents >= 3 &&\n+\t\tgraph->commit_index < (graph->num_columns - 1));\n+}\n+\n void graph_update(struct git_graph *graph, struct commit *commit)\n {\n \tstruct commit_list *parent;\n@@ -622,13 +615,6 @@ void graph_update(struct git_graph *graph, struct commit *commit)\n \t\tgraph->num_parents++;\n \t}\n \n-\t/*\n-\t * Store the old commit_index in prev_commit_index.\n-\t * graph_update_columns() will update graph->commit_index for this\n-\t * commit.\n-\t */\n-\tgraph->prev_commit_index = graph->commit_index;\n-\n \t/*\n \t * Call graph_update_columns() to update\n \t * columns, new_columns, and mapping.\n@@ -639,9 +625,6 @@ void graph_update(struct git_graph *graph, struct commit *commit)\n \n \t/*\n \t * Update graph->state.\n-\t * Note that we don't call graph_update_state() here, since\n-\t * we don't want to update graph->prev_state.  No line for\n-\t * graph->state was ever printed.\n \t *\n \t * If the previous commit didn't get to the GRAPH_PADDING state,\n \t * it never finished its output.  Goto GRAPH_SKIP, to print out\n@@ -657,8 +640,7 @@ void graph_update(struct git_graph *graph, struct commit *commit)\n \t */\n \tif (graph->state != GRAPH_PADDING)\n \t\tgraph->state = GRAPH_SKIP;\n-\telse if (graph->num_parents >= 3 &&\n-\t\t graph->commit_index < (graph->num_columns - 1))\n+\telse if (need_pre_commit(graph))\n \t\tgraph->state = GRAPH_PRE_COMMIT;\n \telse\n \t\tgraph->state = GRAPH_COMMIT;\n@@ -742,8 +724,7 @@ static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)\n \tstrbuf_addstr(sb, \"...\");\n \tgraph_pad_horizontally(graph, sb, 3);\n \n-\tif (graph->num_parents >= 3 &&\n-\t    graph->commit_index < (graph->num_columns - 1))\n+\tif (need_pre_commit(graph))\n \t\tgraph_update_state(graph, GRAPH_PRE_COMMIT);\n \telse\n \t\tgraph_update_state(graph, GRAPH_COMMIT);\n@@ -763,14 +744,16 @@ static void graph_output_pre_commit_line(struct git_graph *graph,\n \t *\n \t * We need 2 extra rows for every parent over 2.\n \t */\n-\tassert(graph->num_parents >= 3);\n+\tassert(graph->num_parents >= 2);\n \tnum_expansion_rows = (graph->num_parents - 2) * 2;\n+\tif (num_expansion_rows == 0)\n+\t\tgraph->expansion_row = -1;\n \n \t/*\n \t * graph->expansion_row tracks the current expansion row we are on.\n \t * It should be in the range [0, num_expansion_rows - 1]\n \t */\n-\tassert(0 <= graph->expansion_row &&\n+\tassert(-1 <= graph->expansion_row &&\n \t       graph->expansion_row < num_expansion_rows);\n \n \t/*\n@@ -783,25 +766,9 @@ static void graph_output_pre_commit_line(struct git_graph *graph,\n \t\tif (col->commit == graph->commit) {\n \t\t\tseen_this = 1;\n \t\t\tstrbuf_write_column(sb, col, '|');\n-\t\t\tstrbuf_addchars(sb, ' ', graph->expansion_row);\n-\t\t\tchars_written += 1 + graph->expansion_row;\n-\t\t} else if (seen_this && (graph->expansion_row == 0)) {\n-\t\t\t/*\n-\t\t\t * This is the first line of the pre-commit output.\n-\t\t\t * If the previous commit was a merge commit and\n-\t\t\t * ended in the GRAPH_POST_MERGE state, all branch\n-\t\t\t * lines after graph->prev_commit_index were\n-\t\t\t * printed as \"\\\" on the previous line.  Continue\n-\t\t\t * to print them as \"\\\" on this line.  Otherwise,\n-\t\t\t * print the branch lines as \"|\".\n-\t\t\t */\n-\t\t\tif (graph->prev_state == GRAPH_POST_MERGE &&\n-\t\t\t    graph->prev_commit_index < i)\n-\t\t\t\tstrbuf_write_column(sb, col, '\\\\');\n-\t\t\telse\n-\t\t\t\tstrbuf_write_column(sb, col, '|');\n-\t\t\tchars_written++;\n-\t\t} else if (seen_this && (graph->expansion_row > 0)) {\n+\t\t\tstrbuf_addchars(sb, ' ', graph->expansion_row + 1);\n+\t\t\tchars_written += 2 + graph->expansion_row;\n+\t\t} else if (seen_this) {\n \t\t\tstrbuf_write_column(sb, col, '\\\\');\n \t\t\tchars_written++;\n \t\t} else {\n@@ -887,8 +854,7 @@ static int graph_draw_octopus_merge(struct git_graph *graph,\n \tint i;\n \tfor (i = 0; i < dashful_parents; i++) {\n \t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col], '-');\n-\t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col],\n-\t\t\t\t    i == dashful_parents-1 ? '.' : '-');\n+\t\tstrbuf_write_column(sb, &graph->new_columns[i+first_col], '-');\n \t}\n \treturn 2 * dashful_parents;\n }\n@@ -896,7 +862,8 @@ static int graph_draw_octopus_merge(struct git_graph *graph,\n static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)\n {\n \tint seen_this = 0;\n-\tint i, chars_written;\n+\tint i, j, k, chars_written;\n+\tchar draw_ch;\n \n \t/*\n \t * Output the row containing this commit\n@@ -910,6 +877,7 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)\n \tfor (i = 0; i <= graph->num_columns; i++) {\n \t\tstruct column *col = &graph->columns[i];\n \t\tstruct commit *col_commit;\n+\t\tint add_space = 1;\n \t\tif (i == graph->num_columns) {\n \t\t\tif (seen_this)\n \t\t\t\tbreak;\n@@ -923,138 +891,76 @@ static void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)\n \t\t\tgraph_output_commit_char(graph, sb);\n \t\t\tchars_written++;\n \n-\t\t\tif (graph->num_parents > 2)\n+\t\t\tdraw_ch = graph->num_parents == 2 ? '_' : 0;\n+\t\t\tif (graph->num_parents > 2) {\n \t\t\t\tchars_written += graph_draw_octopus_merge(graph,\n \t\t\t\t\t\t\t\t\t  sb);\n-\t\t} else if (seen_this && (graph->num_parents > 2)) {\n-\t\t\tstrbuf_write_column(sb, col, '\\\\');\n-\t\t\tchars_written++;\n-\t\t} else if (seen_this && (graph->num_parents == 2)) {\n-\t\t\t/*\n-\t\t\t * This is a 2-way merge commit.\n-\t\t\t * There is no GRAPH_PRE_COMMIT stage for 2-way\n-\t\t\t * merges, so this is the first line of output\n-\t\t\t * for this commit.  Check to see what the previous\n-\t\t\t * line of output was.\n-\t\t\t *\n-\t\t\t * If it was GRAPH_POST_MERGE, the branch line\n-\t\t\t * coming into this commit may have been '\\',\n-\t\t\t * and not '|' or '/'.  If so, output the branch\n-\t\t\t * line as '\\' on this line, instead of '|'.  This\n-\t\t\t * makes the output look nicer.\n-\t\t\t */\n-\t\t\tif (graph->prev_state == GRAPH_POST_MERGE &&\n-\t\t\t    graph->prev_commit_index < i)\n-\t\t\t\tstrbuf_write_column(sb, col, '\\\\');\n-\t\t\telse\n-\t\t\t\tstrbuf_write_column(sb, col, '|');\n-\t\t\tchars_written++;\n-\t\t} else {\n-\t\t\tstrbuf_write_column(sb, col, '|');\n-\t\t\tchars_written++;\n-\t\t}\n-\t\tstrbuf_addch(sb, ' ');\n-\t\tchars_written++;\n-\t}\n-\n-\tgraph_pad_horizontally(graph, sb, chars_written);\n-\n-\t/*\n-\t * Update graph->state\n-\t */\n-\tif (graph->num_parents > 1)\n-\t\tgraph_update_state(graph, GRAPH_POST_MERGE);\n-\telse if (graph_is_mapping_correct(graph))\n-\t\tgraph_update_state(graph, GRAPH_PADDING);\n-\telse\n-\t\tgraph_update_state(graph, GRAPH_COLLAPSING);\n-}\n-\n-static struct column *find_new_column_by_commit(struct git_graph *graph,\n-\t\t\t\t\t\tstruct commit *commit)\n-{\n-\tint i;\n-\tfor (i = 0; i < graph->num_new_columns; i++) {\n-\t\tif (graph->new_columns[i].commit == commit)\n-\t\t\treturn &graph->new_columns[i];\n-\t}\n-\treturn NULL;\n-}\n-\n-static void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)\n-{\n-\tint seen_this = 0;\n-\tint i, j, chars_written;\n-\n-\t/*\n-\t * Output the post-merge row\n-\t */\n-\tchars_written = 0;\n-\tfor (i = 0; i <= graph->num_columns; i++) {\n-\t\tstruct column *col = &graph->columns[i];\n-\t\tstruct commit *col_commit;\n-\t\tif (i == graph->num_columns) {\n-\t\t\tif (seen_this)\n-\t\t\t\tbreak;\n-\t\t\tcol_commit = graph->commit;\n-\t\t} else {\n-\t\t\tcol_commit = col->commit;\n-\t\t}\n-\n-\t\tif (col_commit == graph->commit) {\n-\t\t\t/*\n-\t\t\t * Since the current commit is a merge find\n-\t\t\t * the columns for the parent commits in\n-\t\t\t * new_columns and use those to format the\n-\t\t\t * edges.\n-\t\t\t */\n-\t\t\tstruct commit_list *parents = NULL;\n-\t\t\tstruct column *par_column;\n-\t\t\tseen_this = 1;\n-\t\t\tparents = first_interesting_parent(graph);\n-\t\t\tassert(parents);\n-\t\t\tpar_column = find_new_column_by_commit(graph, parents->item);\n-\t\t\tassert(par_column);\n-\n-\t\t\tstrbuf_write_column(sb, par_column, '|');\n-\t\t\tchars_written++;\n-\t\t\tfor (j = 0; j < graph->num_parents - 1; j++) {\n-\t\t\t\tparents = next_interesting_parent(graph, parents);\n-\t\t\t\tassert(parents);\n-\t\t\t\tpar_column = find_new_column_by_commit(graph, parents->item);\n-\t\t\t\tassert(par_column);\n-\t\t\t\tstrbuf_write_column(sb, par_column, '\\\\');\n-\t\t\t\tstrbuf_addch(sb, ' ');\n+\t\t\t\tdraw_ch = '.';\n \t\t\t}\n-\t\t\tchars_written += j * 2;\n-\t\t} else if (seen_this) {\n-\t\t\tstrbuf_write_column(sb, col, '\\\\');\n-\t\t\tstrbuf_addch(sb, ' ');\n-\t\t\tchars_written += 2;\n+\t\t\tif (graph->num_parents > 1) {\n+\t\t\t\tj = i+1, k = i+2;\n+\t\t\t\tif (i > 0 && graph->mapping[j*2] == i-1)\n+\t\t\t\t\tcol = &graph->new_columns[i-1];\n+\t\t\t\telse\n+\t\t\t\t\tcol = &graph->new_columns[i+graph->num_parents-1];\n+\t\t\t\t/* \n+\t\t\t\t   optimize collapse after merge case:\n+\t\t\t\t   i j k\n+\t\t\t\t   | * <hash> some commit \n+\t\t\t\t   *. \\ <hash> merge branch with another commit\n+\t\t\t\t   | |/    <--- collapse line\n+\t\t\t\t   | * <hash> another commit\n+\n+\t\t\t\t   this happens if the mapping of the second next\n+\t\t\t\t   column merges with the next column\n+\t\t\t\t   remember this by marking seen_this = 2\n+\t\t\t\t   adjust mapping array because we fixed it here\n+\n+\t\t\t\t   output:\n+\t\t\t\t   | * <hash> some commit\n+\t\t\t\t   *.| <hash> merge branch with another commit\n+\t\t\t\t   | * <hash> another commit\n+\n+\t\t\t\t   this saves a line, plus the merge commit is\n+\t\t\t\t   not indented anymore relative to what's merged\n+\t\t\t\t*/\n+\t\t\t\tif (graph->mapping[j*2] == j && graph->mapping[k*2] == j) {\n+\t\t\t\t\tfor (; k*2 < graph->mapping_size; k++)\n+\t\t\t\t\t\tgraph->mapping[k*2] = k;\n+\t\t\t\t\tadd_space = 0;\n+\t\t\t\t\tseen_this = 2;  /* draw a '|' */\n+\t\t\t\t}\n+\t\t\t}\n+\t\t} else if (seen_this == 1 && (graph->num_parents >= 2)) {\n+\t\t\tdraw_ch = '\\\\';\n \t\t} else {\n-\t\t\tstrbuf_write_column(sb, col, '|');\n-\t\t\tstrbuf_addch(sb, ' ');\n-\t\t\tchars_written += 2;\n+\t\t\tdraw_ch = '|';\n \t\t}\n+\t\tif (draw_ch)\n+\t\t\tstrbuf_write_column(sb, col, draw_ch);\n+\t\tif (add_space)\n+\t\t\tstrbuf_addch(sb, ' ');\n+\t\tchars_written += 1 + add_space;\n \t}\n \n-\tgraph_pad_horizontally(graph, sb, chars_written);\n-\n \t/*\n \t * Update graph->state\n \t */\n-\tif (graph_is_mapping_correct(graph))\n+\tgraph->prev_merge_index = 0xffff;\n+\tif (graph_is_mapping_correct(graph)) {\n \t\tgraph_update_state(graph, GRAPH_PADDING);\n-\telse\n+\t\tif (graph->num_parents > 1)\n+\t\t\tgraph->prev_merge_index = graph->commit_index;\n+\t} else\n \t\tgraph_update_state(graph, GRAPH_COLLAPSING);\n }\n \n static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)\n {\n-\tint i;\n-\tshort used_horizontal = 0;\n+\tint i, j;\n \tint horizontal_edge = -1;\n \tint horizontal_edge_target = -1;\n+\tchar draw_ch;\n \n \t/*\n \t * Clear out the new_mapping array\n@@ -1097,16 +1003,15 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf\n \t\t\t * select this one.\n \t\t\t */\n \t\t\tif (horizontal_edge == -1) {\n-\t\t\t\tint j;\n \t\t\t\thorizontal_edge = i;\n \t\t\t\thorizontal_edge_target = target;\n \t\t\t\t/*\n \t\t\t\t * The variable target is the index of the graph\n-\t\t\t\t * column, and therefore target*2+3 is the\n+\t\t\t\t * column, and therefore target*2+1 is the\n \t\t\t\t * actual screen column of the first horizontal\n \t\t\t\t * line.\n \t\t\t\t */\n-\t\t\t\tfor (j = (target * 2)+3; j < (i - 2); j += 2)\n+\t\t\t\tfor (j = (target * 2)+1; j < i; j += 2)\n \t\t\t\t\tgraph->new_mapping[j] = target;\n \t\t\t}\n \t\t} else if (graph->new_mapping[i - 1] == target) {\n@@ -1158,27 +1063,19 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf\n \t */\n \tfor (i = 0; i < graph->mapping_size; i++) {\n \t\tint target = graph->new_mapping[i];\n-\t\tif (target < 0)\n+\t\tif (target < 0) {\n \t\t\tstrbuf_addch(sb, ' ');\n-\t\telse if (target * 2 == i)\n-\t\t\tstrbuf_write_column(sb, &graph->new_columns[target], '|');\n-\t\telse if (target == horizontal_edge_target &&\n-\t\t\t i != horizontal_edge - 1) {\n-\t\t\t\t/*\n-\t\t\t\t * Set the mappings for all but the\n-\t\t\t\t * first segment to -1 so that they\n-\t\t\t\t * won't continue into the next line.\n-\t\t\t\t */\n-\t\t\t\tif (i != (target * 2)+3)\n-\t\t\t\t\tgraph->new_mapping[i] = -1;\n-\t\t\t\tused_horizontal = 1;\n-\t\t\tstrbuf_write_column(sb, &graph->new_columns[target], '_');\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (target * 2 == i) {\n+\t\t\tdraw_ch = '|';\n \t\t} else {\n-\t\t\tif (used_horizontal && i < horizontal_edge)\n+\t\t\tif (i < horizontal_edge)\n \t\t\t\tgraph->new_mapping[i] = -1;\n-\t\t\tstrbuf_write_column(sb, &graph->new_columns[target], '/');\n-\n+\t\t\tdraw_ch = target == horizontal_edge_target &&\n+\t\t\t\ti != horizontal_edge-1 ? '_' : '/';\n \t\t}\n+\t\tstrbuf_write_column(sb, &graph->new_columns[target], draw_ch);\n \t}\n \n \tgraph_pad_horizontally(graph, sb, graph->mapping_size);\n@@ -1212,9 +1109,6 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb)\n \tcase GRAPH_COMMIT:\n \t\tgraph_output_commit_line(graph, sb);\n \t\treturn 1;\n-\tcase GRAPH_POST_MERGE:\n-\t\tgraph_output_post_merge_line(graph, sb);\n-\t\treturn 0;\n \tcase GRAPH_COLLAPSING:\n \t\tgraph_output_collapsing_line(graph, sb);\n \t\treturn 0;\n@@ -1258,11 +1152,6 @@ static void graph_padding_line(struct git_graph *graph, struct strbuf *sb)\n \t}\n \n \tgraph_pad_horizontally(graph, sb, chars_written);\n-\n-\t/*\n-\t * Update graph->prev_state since we have output a padding line\n-\t */\n-\tgraph->prev_state = GRAPH_PADDING;\n }\n \n int graph_is_commit_finished(struct git_graph const *graph)\n-- \n2.17.1\n\n"}]}