{"thread":{"id":"13369","subject":"[PATCH 0/3] log --graph and rev-list --graph","startedAt":"2008-05-04T10:36:51Z","lastAt":"2008-05-06T19:03:05Z","messageCount":13,"participants":["Adam Simpkins","Teemu Likonen","Ping Yin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"76007","messageId":"1209897414-10091-1-git-send-email-adam@adamsimpkins.net","threadId":"13369","inReplyTo":null,"subject":"[PATCH 0/3] log --graph and rev-list --graph","fromName":"Adam Simpkins","fromEmail":"adam@adamsimpkins.net","sentAt":"2008-05-04T10:36:51Z","receivedAt":"2008-05-04T10:36:51Z","isPatch":true,"sender":{"key":"adam@adamsimpkins.net","avatar":"https://gravatar.com/avatar/d3fd2c0b3e2d2136b56e95726ee03227bee4eb562f627dcd3ebca0623fa05054?d=mp&s=160"},"body":"This patch series adds a new --graph option to the log and rev-list\ncommands.  This is pretty much the same code that I sent out in early\nApril, but updated to work with the log entry termination fixes in the\nlatest master branch.\n\nAdam Simpkins (3):\n  revision API: split parent rewriting and parent printing options\n  Add history graph API\n  log and rev-list: add --graph option\n\n Documentation/rev-list-options.txt            |   10 +\n Documentation/technical/api-history-graph.txt |  179 +++++\n Makefile                                      |    2 +\n builtin-rev-list.c                            |   52 ++-\n graph.c                                       |  903 +++++++++++++++++++++++++\n graph.h                                       |  121 ++++\n log-tree.c                                    |   80 ++-\n revision.c                                    |   33 +-\n revision.h                                    |    9 +-\n 9 files changed, 1369 insertions(+), 20 deletions(-)\n create mode 100644 Documentation/technical/api-history-graph.txt\n create mode 100644 graph.c\n create mode 100644 graph.h\n"},{"id":"76008","messageId":"1209897414-10091-2-git-send-email-adam@adamsimpkins.net","threadId":"13369","inReplyTo":"1209897414-10091-1-git-send-email-adam@adamsimpkins.net","subject":"[PATCH 1/3] revision API: split parent rewriting and parent printing options","fromName":"Adam Simpkins","fromEmail":"adam@adamsimpkins.net","sentAt":"2008-05-04T10:36:52Z","receivedAt":"2008-05-04T10:36:52Z","isPatch":true,"sender":{"key":"adam@adamsimpkins.net","avatar":"https://gravatar.com/avatar/d3fd2c0b3e2d2136b56e95726ee03227bee4eb562f627dcd3ebca0623fa05054?d=mp&s=160"},"body":"This change allows parent rewriting to be performed without causing\nthe log and rev-list commands to print the parents.\n\nSigned-off-by: Adam Simpkins <adam@adamsimpkins.net>\n---\n builtin-rev-list.c |    2 +-\n log-tree.c         |    4 ++--\n revision.c         |    7 ++++---\n revision.h         |    3 ++-\n 4 files changed, 9 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex edc0bd3..476a870 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -77,7 +77,7 @@ static void show_commit(struct commit *commit)\n \t\t      stdout);\n \telse\n \t\tfputs(sha1_to_hex(commit->object.sha1), stdout);\n-\tif (revs.parents) {\n+\tif (revs.print_parents) {\n \t\tstruct commit_list *parents = commit->parents;\n \t\twhile (parents) {\n \t\t\tprintf(\" %s\", sha1_to_hex(parents->item->object.sha1));\ndiff --git a/log-tree.c b/log-tree.c\nindex d3fb0e5..74829d7 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -231,7 +231,7 @@ void show_log(struct rev_info *opt)\n \t\t\t\tputchar('>');\n \t\t}\n \t\tfputs(diff_unique_abbrev(commit->object.sha1, abbrev_commit), stdout);\n-\t\tif (opt->parents)\n+\t\tif (opt->print_parents)\n \t\t\tshow_parents(commit, abbrev_commit);\n \t\tshow_decorations(commit);\n \t\tputchar(opt->diffopt.line_termination);\n@@ -271,7 +271,7 @@ void show_log(struct rev_info *opt)\n \t\t}\n \t\tfputs(diff_unique_abbrev(commit->object.sha1, abbrev_commit),\n \t\t      stdout);\n-\t\tif (opt->parents)\n+\t\tif (opt->print_parents)\n \t\t\tshow_parents(commit, abbrev_commit);\n \t\tif (parent)\n \t\t\tprintf(\" (from %s)\",\ndiff --git a/revision.c b/revision.c\nindex 4231ea2..a813304 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1105,7 +1105,8 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \t\t\t\t}\n \t\t\t}\n \t\t\tif (!strcmp(arg, \"--parents\")) {\n-\t\t\t\trevs->parents = 1;\n+\t\t\t\trevs->rewrite_parents = 1;\n+\t\t\t\trevs->print_parents = 1;\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (!strcmp(arg, \"--dense\")) {\n@@ -1524,13 +1525,13 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\t/* Commit without changes? */\n \t\tif (commit->object.flags & TREESAME) {\n \t\t\t/* drop merges unless we want parenthood */\n-\t\t\tif (!revs->parents)\n+\t\t\tif (!revs->rewrite_parents)\n \t\t\t\treturn commit_ignore;\n \t\t\t/* non-merge - always ignore it */\n \t\t\tif (!commit->parents || !commit->parents->next)\n \t\t\t\treturn commit_ignore;\n \t\t}\n-\t\tif (revs->parents && rewrite_parents(revs, commit) < 0)\n+\t\tif (revs->rewrite_parents && rewrite_parents(revs, commit) < 0)\n \t\t\treturn commit_error;\n \t}\n \treturn commit_show;\ndiff --git a/revision.h b/revision.h\nindex 31217f8..201bd97 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -46,7 +46,8 @@ struct rev_info {\n \t\t\tunpacked:1, /* see also ignore_packed below */\n \t\t\tboundary:2,\n \t\t\tleft_right:1,\n-\t\t\tparents:1,\n+\t\t\trewrite_parents:1,\n+\t\t\tprint_parents:1,\n \t\t\treverse:1,\n \t\t\tcherry_pick:1,\n \t\t\tfirst_parent_only:1;\n-- \n1.5.5.1.128.gc15ea\n"},{"id":"76010","messageId":"1209897414-10091-3-git-send-email-adam@adamsimpkins.net","threadId":"13369","inReplyTo":"1209897414-10091-2-git-send-email-adam@adamsimpkins.net","subject":"[PATCH 2/3] Add history graph API","fromName":"Adam Simpkins","fromEmail":"adam@adamsimpkins.net","sentAt":"2008-05-04T10:36:53Z","receivedAt":"2008-05-04T10:36:53Z","isPatch":true,"sender":{"key":"adam@adamsimpkins.net","avatar":"https://gravatar.com/avatar/d3fd2c0b3e2d2136b56e95726ee03227bee4eb562f627dcd3ebca0623fa05054?d=mp&s=160"},"body":"This new API allows the commit history to be displayed as a text-based\ngraphical representation.\n\nSigned-off-by: Adam Simpkins <adam@adamsimpkins.net>\n---\n Documentation/technical/api-history-graph.txt |  176 +++++\n Makefile                                      |    2 +\n graph.c                                       |  903 +++++++++++++++++++++++++\n graph.h                                       |  121 ++++\n 4 files changed, 1202 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/technical/api-history-graph.txt\n create mode 100644 graph.c\n create mode 100644 graph.h\n\ndiff --git a/Documentation/technical/api-history-graph.txt b/Documentation/technical/api-history-graph.txt\nnew file mode 100644\nindex 0000000..5f6465f\n--- /dev/null\n+++ b/Documentation/technical/api-history-graph.txt\n@@ -0,0 +1,176 @@\n+history graph API\n+=================\n+\n+The graph API is used to draw a text-based representation of the commit\n+history.  The API generates the graph in a line-by-line fashion.\n+\n+Functions\n+---------\n+\n+Core functions:\n+\n+* `graph_init()` creates a new `struct git_graph`\n+\n+* `graph_release()` destroys a `struct git_graph`, and frees the memory\n+  associated with it.\n+\n+* `graph_update()` moves the graph to a new commit.\n+\n+* `graph_next_line()` outputs the next line of the graph into a strbuf.  It\n+  does not add a terminating newline.\n+\n+* `graph_padding_line()` outputs a line of vertical padding in the graph.  It\n+  is similar to `graph_next_line()`, but is guaranteed to never print the line\n+  containing the current commit.  Where `graph_next_line()` would print the\n+  commit line next, `graph_padding_line()` prints a line that simply extends\n+  all branch lines downwards one row, leaving their positions unchanged.\n+\n+* `graph_is_commit_finished()` determines if the graph has output all lines\n+  necessary for the current commit.  If `graph_update()` is called before all\n+  lines for the current commit have been printed, the next call to\n+  `graph_next_line()` will output an ellipsis, to indicate that a portion of\n+  the graph was omitted.\n+\n+The following utility functions are wrappers around `graph_next_line()` and\n+`graph_is_commit_finished()`.  They always print the output to stdout.\n+They can all be called with a NULL graph argument, in which case no graph\n+output will be printed.\n+\n+* `graph_show_commit()` calls `graph_next_line()` until it returns non-zero.\n+  This prints all graph lines up to, and including, the line containing this\n+  commit.  Output is printed to stdout.  The last line printed does not contain\n+  a terminating newline.  This should not be called if the commit line has\n+  already been printed, or it will loop forever.\n+\n+* `graph_show_oneline()` calls `graph_next_line()` and prints the result to\n+  stdout.  The line printed does not contain a terminating newline.\n+\n+* `graph_show_padding()` calls `graph_padding_line()` and prints the result to\n+  stdout.  The line printed does not contain a terminating newline.\n+\n+* `graph_show_remainder()` calls `graph_next_line()` until\n+  `graph_is_commit_finished()` returns non-zero.  Output is printed to stdout.\n+  The last line printed does not contain a terminating newline.  Returns 1 if\n+  output was printed, and 0 if no output was necessary.\n+\n+* `graph_show_strbuf()` prints the specified strbuf to stdout, prefixing all\n+  lines but the first with a graph line.  The caller is responsible for\n+  ensuring graph output for the first line has already been printed to stdout.\n+  (This can be done with `graph_show_commit()` or `graph_show_oneline()`.)  If\n+  a NULL graph is supplied, the strbuf is printed as-is.\n+\n+* `graph_show_commit_msg()` is similar to `graph_show_strbuf()`, but it also\n+  prints the remainder of the graph, if more lines are needed after the strbuf\n+  ends.  It is better than directly calling `graph_show_strbuf()` followed by\n+  `graph_show_remainder()` since it properly handles buffers that do not end in\n+  a terminating newline.  The output printed by `graph_show_commit_msg()` will\n+  end in a newline if and only if the strbuf ends in a newline.\n+\n+Data structure\n+--------------\n+`struct git_graph` is an opaque data type used to store the current graph\n+state.\n+\n+Calling sequence\n+----------------\n+\n+* Create a `struct git_graph` by calling `graph_init()`.\n+\n+* Use the revision walking API to walk through a group of contiguous commits.\n+\n+* For each commit traversed, call `graph_update()` to move the graph to the\n+  next commit.  Once `graph_update()` has been called, call `graph_next_line()`\n+  repeatedly, until `graph_is_commit_finished()` returns non-zero.  Each call\n+  to `graph_next_line()` will output a single line of the graph.  The resulting\n+  lines will not contain any newlines.  `graph_next_line()` returns 1 if the\n+  resulting line contains the current commit, or 0 if this is merely a line\n+  needed to adjust the graph before or after the current commit.  This return\n+  value can be used to determine where to print the commit summary information\n+  alongside the graph output.\n+\n+Limitations\n+-----------\n+\n+* `graph_update()` must be called with commits in topological order.  It should\n+  not be called on a commit if it has already been invoked with an ancestor of\n+  that commit, or the graph output will be incorrect.\n+\n+* `graph_update()` must be called on a contiguous group of commits.  If\n+  `graph_update()` is called on a particular commit, it should later be called\n+  on all parents of that commit.  Parents must not be skipped, or the graph\n+  output will appear incorrect.\n++\n+`graph_update()` may be used on a pruned set of commits only if the parent list\n+has been rewritten so as to include only ancestors from the pruned set.\n+\n+* The graph API does not currently support reverse commit ordering.  In\n+  order to implement reverse ordering, the graphing API needs an\n+  (efficient) mechanism to find the children of a commit.\n+\n+Sample usage\n+------------\n+\n+------------\n+struct commit *commit;\n+struct git_graph *graph = graph_init();\n+\n+while ((commit = get_revision(opts)) != NULL) {\n+\tgraph_update(graph, commit);\n+\twhile (!graph_is_commit_finished(graph))\n+\t{\n+\t\tstruct strbuf sb;\n+\t\tint is_commit_line;\n+\n+\t\tstrbuf_init(&sb, 0);\n+\t\tis_commit_line = graph_next_line(graph, &sb);\n+\t\tfputs(sb.buf, stdout);\n+\n+\t\tif (is_commit_line)\n+\t\t\tlog_tree_commit(opts, commit);\n+\t\telse\n+\t\t\tputchar(opts->diffopt.line_termination);\n+\t}\n+}\n+\n+graph_release(graph);\n+------------\n+\n+Sample output\n+-------------\n+\n+The following is an example of the output from the graph API.  This output does\n+not include any commit summary information--callers are responsible for\n+outputting that information, if desired.\n+\n+------------\n+*\n+*\n+M\n+|\\\n+* |\n+| | *\n+| \\ \\\n+|  \\ \\\n+M-. \\ \\\n+|\\ \\ \\ \\\n+| | * | |\n+| | | | | *\n+| | | | | *\n+| | | | | M\n+| | | | | |\\\n+| | | | | | *\n+| * | | | | |\n+| | | | | M  \\\n+| | | | | |\\  |\n+| | | | * | | |\n+| | | | * | | |\n+* | | | | | | |\n+| |/ / / / / /\n+|/| / / / / /\n+* | | | | | |\n+|/ / / / / /\n+* | | | | |\n+| | | | | *\n+| | | | |/\n+| | | | *\n+------------\ndiff --git a/Makefile b/Makefile\nindex 9d84c8d..d42b117 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -346,6 +346,7 @@ LIB_H += diff.h\n LIB_H += dir.h\n LIB_H += fsck.h\n LIB_H += git-compat-util.h\n+LIB_H += graph.h\n LIB_H += grep.h\n LIB_H += hash.h\n LIB_H += list-objects.h\n@@ -411,6 +412,7 @@ LIB_OBJS += entry.o\n LIB_OBJS += environment.o\n LIB_OBJS += exec_cmd.o\n LIB_OBJS += fsck.o\n+LIB_OBJS += graph.o\n LIB_OBJS += grep.o\n LIB_OBJS += hash.o\n LIB_OBJS += help.o\ndiff --git a/graph.c b/graph.c\nnew file mode 100644\nindex 0000000..b575d10\n--- /dev/null\n+++ b/graph.c\n@@ -0,0 +1,903 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"graph.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+\n+/*\n+ * TODO:\n+ * - Add colors to the graph.\n+ *   Pick a color for each column, and print all characters\n+ *   in that column with the specified color.\n+ *\n+ * - Limit the number of columns, similar to the way gitk does.\n+ *   If we reach more than a specified number of columns, omit\n+ *   sections of some columns.\n+ *\n+ * - The output during the GRAPH_PRE_COMMIT and GRAPH_COLLAPSING states\n+ *   could be made more compact by printing horizontal lines, instead of\n+ *   long diagonal lines.  For example, during collapsing, something like\n+ *   this:          instead of this:\n+ *   | | | | |      | | | | |\n+ *   | |_|_|/       | | | |/\n+ *   |/| | |        | | |/|\n+ *   | | | |        | |/| |\n+ *                  |/| | |\n+ *                  | | | |\n+ *\n+ *   If there are several parallel diagonal lines, they will need to be\n+ *   replaced with horizontal lines on subsequent rows.\n+ */\n+\n+struct column {\n+\t/*\n+\t * The parent commit of this column.\n+\t */\n+\tstruct commit *commit;\n+\t/*\n+\t * XXX: Once we add support for colors, struct column could also\n+\t * contain the color of its branch line.\n+\t */\n+};\n+\n+enum graph_state {\n+\tGRAPH_PADDING,\n+\tGRAPH_SKIP,\n+\tGRAPH_PRE_COMMIT,\n+\tGRAPH_COMMIT,\n+\tGRAPH_POST_MERGE,\n+\tGRAPH_COLLAPSING\n+};\n+\n+struct git_graph {\n+\t/*\n+\t * The commit currently being processed\n+\t */\n+\tstruct commit *commit;\n+\t/*\n+\t * The number of parents this commit has.\n+\t * (Stored so we don't have to walk over them each time we need\n+\t * this number)\n+\t */\n+\tint num_parents;\n+\t/*\n+\t * The next expansion row to print\n+\t * when state is GRAPH_PRE_COMMIT\n+\t */\n+\tint expansion_row;\n+\t/*\n+\t * The current output state.\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 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+\t * that can be stored in the mapping and new_mapping arrays.\n+\t */\n+\tint column_capacity;\n+\t/*\n+\t * The number of columns (also called \"branch lines\" in some places)\n+\t */\n+\tint num_columns;\n+\t/*\n+\t * The number of columns in the new_columns array\n+\t */\n+\tint num_new_columns;\n+\t/*\n+\t * The number of entries in the mapping array\n+\t */\n+\tint mapping_size;\n+\t/*\n+\t * The column state before we output the current commit.\n+\t */\n+\tstruct column *columns;\n+\t/*\n+\t * The new column state after we output the current commit.\n+\t * Only valid when state is GRAPH_COLLAPSING.\n+\t */\n+\tstruct column *new_columns;\n+\t/*\n+\t * An array that tracks the current state of each\n+\t * character in the output line during state GRAPH_COLLAPSING.\n+\t * Each entry is -1 if this character is empty, or a non-negative\n+\t * integer if the character contains a branch line.  The value of\n+\t * the integer indicates the target position for this branch line.\n+\t * (I.e., this array maps the current column positions to their\n+\t * desired positions.)\n+\t *\n+\t * The maximum capacity of this array is always\n+\t * sizeof(int) * 2 * column_capacity.\n+\t */\n+\tint *mapping;\n+\t/*\n+\t * A temporary array for computing the next mapping state\n+\t * while we are outputting a mapping line.  This is stored as part\n+\t * of the git_graph simply so we don't have to allocate a new\n+\t * temporary array each time we have to output a collapsing line.\n+\t */\n+\tint *new_mapping;\n+};\n+\n+struct git_graph *graph_init()\n+{\n+\tstruct git_graph *graph = xmalloc(sizeof(struct git_graph));\n+\tgraph->commit = NULL;\n+\tgraph->num_parents = 0;\n+\tgraph->expansion_row = 0;\n+\tgraph->state = GRAPH_PADDING;\n+\tgraph->num_columns = 0;\n+\tgraph->num_new_columns = 0;\n+\tgraph->mapping_size = 0;\n+\n+\t/*\n+\t * Allocate a reasonably large default number of columns\n+\t * We'll automatically grow columns later if we need more room.\n+\t */\n+\tgraph->column_capacity = 30;\n+\tgraph->columns = xmalloc(sizeof(struct column) *\n+\t\t\t\t graph->column_capacity);\n+\tgraph->new_columns = xmalloc(sizeof(struct column) *\n+\t\t\t\t     graph->column_capacity);\n+\tgraph->mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity);\n+\tgraph->new_mapping = xmalloc(sizeof(int) * 2 * graph->column_capacity);\n+\n+\treturn graph;\n+}\n+\n+void graph_release(struct git_graph *graph)\n+{\n+\tfree(graph->columns);\n+\tfree(graph->new_columns);\n+\tfree(graph->mapping);\n+\tfree(graph);\n+}\n+\n+static void graph_ensure_capacity(struct git_graph *graph, int num_columns)\n+{\n+\tif (graph->column_capacity >= num_columns)\n+\t\treturn;\n+\n+\tdo {\n+\t\tgraph->column_capacity *= 2;\n+\t} while (graph->column_capacity < num_columns);\n+\n+\tgraph->columns = xrealloc(graph->columns,\n+\t\t\t\t  sizeof(struct column) *\n+\t\t\t\t  graph->column_capacity);\n+\tgraph->new_columns = xrealloc(graph->new_columns,\n+\t\t\t\t      sizeof(struct column) *\n+\t\t\t\t      graph->column_capacity);\n+\tgraph->mapping = xrealloc(graph->mapping,\n+\t\t\t\t  sizeof(int) * 2 * graph->column_capacity);\n+\tgraph->new_mapping = xrealloc(graph->new_mapping,\n+\t\t\t\t      sizeof(int) * 2 * graph->column_capacity);\n+}\n+\n+static void graph_insert_into_new_columns(struct git_graph *graph,\n+\t\t\t\t\t  struct commit *commit,\n+\t\t\t\t\t  int *mapping_index)\n+{\n+\tint i;\n+\n+\t/*\n+\t * Ignore uinteresting and pruned commits\n+\t */\n+\tif (commit->object.flags & (UNINTERESTING | TREESAME))\n+\t\treturn;\n+\n+\t/*\n+\t * If the commit is already in the new_columns list, we don't need to\n+\t * add it.  Just update the mapping correctly.\n+\t */\n+\tfor (i = 0; i < graph->num_new_columns; i++) {\n+\t\tif (graph->new_columns[i].commit == commit) {\n+\t\t\tgraph->mapping[*mapping_index] = i;\n+\t\t\t*mapping_index += 2;\n+\t\t\treturn;\n+\t\t}\n+\t}\n+\n+\t/*\n+\t * This commit isn't already in new_columns.  Add it.\n+\t */\n+\tgraph->new_columns[graph->num_new_columns].commit = commit;\n+\tgraph->mapping[*mapping_index] = graph->num_new_columns;\n+\t*mapping_index += 2;\n+\tgraph->num_new_columns++;\n+}\n+\n+static void graph_update_columns(struct git_graph *graph)\n+{\n+\tstruct commit_list *parent;\n+\tstruct column *tmp_columns;\n+\tint max_new_columns;\n+\tint mapping_idx;\n+\tint i, seen_this;\n+\n+\t/*\n+\t * Swap graph->columns with graph->new_columns\n+\t * graph->columns contains the state for the previous commit,\n+\t * and new_columns now contains the state for our commit.\n+\t *\n+\t * We'll re-use the old columns array as storage to compute the new\n+\t * columns list for the commit after this one.\n+\t */\n+\ttmp_columns = graph->columns;\n+\tgraph->columns = graph->new_columns;\n+\tgraph->num_columns = graph->num_new_columns;\n+\n+\tgraph->new_columns = tmp_columns;\n+\tgraph->num_new_columns = 0;\n+\n+\t/*\n+\t * Now update new_columns and mapping with the information for the\n+\t * commit after this one.\n+\t *\n+\t * First, make sure we have enough room.  At most, there will\n+\t * be graph->num_columns + graph->num_parents columns for the next\n+\t * commit.\n+\t */\n+\tmax_new_columns = graph->num_columns + graph->num_parents;\n+\tgraph_ensure_capacity(graph, max_new_columns);\n+\n+\t/*\n+\t * Clear out graph->mapping\n+\t */\n+\tgraph->mapping_size = 2 * max_new_columns;\n+\tfor (i = 0; i < graph->mapping_size; i++)\n+\t\tgraph->mapping[i] = -1;\n+\n+\t/*\n+\t * Populate graph->new_columns and graph->mapping\n+\t *\n+\t * Some of the parents of this commit may already be in\n+\t * graph->columns.  If so, graph->new_columns should only contain a\n+\t * single entry for each such commit.  graph->mapping should\n+\t * contain information about where each current branch line is\n+\t * supposed to end up after the collapsing is performed.\n+\t */\n+\tseen_this = 0;\n+\tmapping_idx = 0;\n+\tfor (i = 0; i <= graph->num_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 = graph->columns[i].commit;\n+\t\t}\n+\n+\t\tif (col_commit == graph->commit) {\n+\t\t\tseen_this = 1;\n+\t\t\tfor (parent = graph->commit->parents;\n+\t\t\t     parent;\n+\t\t\t     parent = parent->next) {\n+\t\t\t\tgraph_insert_into_new_columns(graph,\n+\t\t\t\t\t\t\t      parent->item,\n+\t\t\t\t\t\t\t      &mapping_idx);\n+\t\t\t}\n+\t\t} else {\n+\t\t\tgraph_insert_into_new_columns(graph, col_commit,\n+\t\t\t\t\t\t      &mapping_idx);\n+\t\t}\n+\t}\n+\n+\t/*\n+\t * Shrink mapping_size to be the minimum necessary\n+\t */\n+\twhile (graph->mapping_size > 1 &&\n+\t       graph->mapping[graph->mapping_size - 1] < 0)\n+\t\tgraph->mapping_size--;\n+}\n+\n+void graph_update(struct git_graph *graph, struct commit *commit)\n+{\n+\tstruct commit_list *parent;\n+\n+\t/*\n+\t * Set the new commit\n+\t */\n+\tgraph->commit = commit;\n+\n+\t/*\n+\t * Count how many parents this commit has\n+\t */\n+\tgraph->num_parents = 0;\n+\tfor (parent = commit->parents; parent; parent = parent->next)\n+\t\tgraph->num_parents++;\n+\n+\t/*\n+\t * Call graph_update_columns() to update\n+\t * columns, new_columns, and mapping.\n+\t */\n+\tgraph_update_columns(graph);\n+\n+\tgraph->expansion_row = 0;\n+\n+\t/*\n+\t * Update graph->state.\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+\t * a line to indicate that portion of the graph is missing.\n+\t *\n+\t * Otherwise, if there are 3 or more parents, we need to print\n+\t * extra rows before the commit, to expand the branch lines around\n+\t * it and make room for it.\n+\t *\n+\t * If there are less than 3 parents, we can immediately print the\n+\t * commit line.\n+\t */\n+\tif (graph->state != GRAPH_PADDING)\n+\t\tgraph->state = GRAPH_SKIP;\n+\telse if (graph->num_parents >= 3)\n+\t\tgraph->state = GRAPH_PRE_COMMIT;\n+\telse\n+\t\tgraph->state = GRAPH_COMMIT;\n+}\n+\n+static int graph_is_mapping_correct(struct git_graph *graph)\n+{\n+\tint i;\n+\n+\t/*\n+\t * The mapping is up to date if each entry is at its target,\n+\t * or is 1 greater than its target.\n+\t * (If it is 1 greater than the target, '/' will be printed, so it\n+\t * will look correct on the next row.)\n+\t */\n+\tfor (i = 0; i < graph->mapping_size; i++) {\n+\t\tint target = graph->mapping[i];\n+\t\tif (target < 0)\n+\t\t\tcontinue;\n+\t\tif (target == (i / 2))\n+\t\t\tcontinue;\n+\t\treturn 0;\n+\t}\n+\n+\treturn 1;\n+}\n+\n+static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)\n+{\n+\t/*\n+\t * Add additional spaces to the end of the strbuf, so that all\n+\t * lines for a particular commit have the same width.\n+\t *\n+\t * This way, fields printed to the right of the graph will remain\n+\t * aligned for the entire commit.\n+\t *\n+\t * This computation results in 3 extra space to the right in most\n+\t * cases, but only 1 extra space if the commit doesn't have any\n+\t * children that have already been displayed in the graph (i.e.,\n+\t * if the current commit isn't in graph->columns).\n+\t */\n+\tsize_t extra;\n+\tsize_t final_width = graph->num_columns + graph->num_parents;\n+\tif (graph->num_parents < 1)\n+\t\tfinal_width++;\n+\tfinal_width *= 2;\n+\n+\tif (sb->len >= final_width)\n+\t\treturn;\n+\n+\textra = final_width - sb->len;\n+\tstrbuf_addf(sb, \"%*s\", extra, \"\");\n+}\n+\n+static void graph_output_padding_line(struct git_graph *graph,\n+\t\t\t\t      struct strbuf *sb)\n+{\n+\tint i;\n+\n+\t/*\n+\t * We could conceivable be called with a NULL commit\n+\t * if our caller has a bug, and invokes graph_next_line()\n+\t * immediately after graph_init(), without first calling\n+\t * graph_update().  Return without outputting anything in this\n+\t * case.\n+\t */\n+\tif (!graph->commit)\n+\t\treturn;\n+\n+\t/*\n+\t * Output a padding row, that leaves all branch lines unchanged\n+\t */\n+\tfor (i = 0; i < graph->num_new_columns; i++) {\n+\t\tstrbuf_addstr(sb, \"| \");\n+\t}\n+\n+\tgraph_pad_horizontally(graph, sb);\n+}\n+\n+static void graph_output_skip_line(struct git_graph *graph, struct strbuf *sb)\n+{\n+\t/*\n+\t * Output an ellipsis to indicate that a portion\n+\t * of the graph is missing.\n+\t */\n+\tstrbuf_addstr(sb, \"...\");\n+\tgraph_pad_horizontally(graph, sb);\n+\n+\tif (graph->num_parents >= 3)\n+\t\tgraph->state = GRAPH_PRE_COMMIT;\n+\telse\n+\t\tgraph->state = GRAPH_COMMIT;\n+}\n+\n+static void graph_output_pre_commit_line(struct git_graph *graph,\n+\t\t\t\t\t struct strbuf *sb)\n+{\n+\tint num_expansion_rows;\n+\tint i, seen_this;\n+\n+\t/*\n+\t * This function formats a row that increases the space around a commit\n+\t * with multiple parents, to make room for it.  It should only be\n+\t * called when there are 3 or more parents.\n+\t *\n+\t * We need 2 extra rows for every parent over 2.\n+\t */\n+\tassert(graph->num_parents >= 3);\n+\tnum_expansion_rows = (graph->num_parents - 2) * 2;\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+\t       graph->expansion_row < num_expansion_rows);\n+\n+\t/*\n+\t * Output the row\n+\t */\n+\tseen_this = 0;\n+\tfor (i = 0; i < graph->num_columns; i++) {\n+\t\tstruct column *col = &graph->columns[i];\n+\t\tif (col->commit == graph->commit) {\n+\t\t\tseen_this = 1;\n+\t\t\tstrbuf_addf(sb, \"| %*s\", graph->expansion_row, \"\");\n+\t\t} else if (seen_this) {\n+\t\t\tstrbuf_addstr(sb, \"\\\\ \");\n+\t\t} else {\n+\t\t\tstrbuf_addstr(sb, \"| \");\n+\t\t}\n+\t}\n+\n+\tgraph_pad_horizontally(graph, sb);\n+\n+\t/*\n+\t * Increment graph->expansion_row,\n+\t * and move to state GRAPH_COMMIT if necessary\n+\t */\n+\tgraph->expansion_row++;\n+\tif (graph->expansion_row >= num_expansion_rows)\n+\t\tgraph->state = GRAPH_COMMIT;\n+}\n+\n+void graph_output_commit_line(struct git_graph *graph, struct strbuf *sb)\n+{\n+\tint seen_this = 0;\n+\tint i, j;\n+\n+\t/*\n+\t * Output the row containing this commit\n+\t * Iterate up to and including graph->num_columns,\n+\t * since the current commit may not be in any of the existing\n+\t * columns.  (This happens when the current commit doesn't have any\n+\t * children that we have already processed.)\n+\t */\n+\tseen_this = 0;\n+\tfor (i = 0; i <= graph->num_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 = graph->columns[i].commit;\n+\t\t}\n+\n+\t\tif (col_commit == graph->commit) {\n+\t\t\tseen_this = 1;\n+\t\t\tif (graph->num_parents > 1)\n+\t\t\t\tstrbuf_addch(sb, 'M');\n+\t\t\telse\n+\t\t\t\tstrbuf_addch(sb, '*');\n+\n+\t\t\tif (graph->num_parents < 2)\n+\t\t\t\tstrbuf_addch(sb, ' ');\n+\t\t\telse if (graph->num_parents == 2)\n+\t\t\t\tstrbuf_addstr(sb, \"  \");\n+\t\t\telse {\n+\t\t\t\tint num_dashes =\n+\t\t\t\t\t((graph->num_parents - 2) * 2) - 1;\n+\t\t\t\tfor (j = 0; j < num_dashes; j++)\n+\t\t\t\t\tstrbuf_addch(sb, '-');\n+\t\t\t\tstrbuf_addstr(sb, \". \");\n+\t\t\t}\n+\t\t} else if (seen_this && (graph->num_parents > 1)) {\n+\t\t\tstrbuf_addstr(sb, \"\\\\ \");\n+\t\t} else {\n+\t\t\tstrbuf_addstr(sb, \"| \");\n+\t\t}\n+\t}\n+\n+\tgraph_pad_horizontally(graph, sb);\n+\n+\t/*\n+\t * Update graph->state\n+\t */\n+\tif (graph->num_parents > 1)\n+\t\tgraph->state = GRAPH_POST_MERGE;\n+\telse if (graph_is_mapping_correct(graph))\n+\t\tgraph->state = GRAPH_PADDING;\n+\telse\n+\t\tgraph->state = GRAPH_COLLAPSING;\n+}\n+\n+void graph_output_post_merge_line(struct git_graph *graph, struct strbuf *sb)\n+{\n+\tint seen_this = 0;\n+\tint i, j;\n+\n+\t/*\n+\t * Output the post-merge row\n+\t */\n+\tfor (i = 0; i <= graph->num_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 = graph->columns[i].commit;\n+\t\t}\n+\n+\t\tif (col_commit == graph->commit) {\n+\t\t\tseen_this = 1;\n+\t\t\tstrbuf_addch(sb, '|');\n+\t\t\tfor (j = 0; j < graph->num_parents - 1; j++)\n+\t\t\t\tstrbuf_addstr(sb, \"\\\\ \");\n+\t\t\tif (graph->num_parents == 2)\n+\t\t\t\tstrbuf_addch(sb, ' ');\n+\t\t} else if (seen_this && (graph->num_parents > 2)) {\n+\t\t\tstrbuf_addstr(sb, \"\\\\ \");\n+\t\t} else {\n+\t\t\tstrbuf_addstr(sb, \"| \");\n+\t\t}\n+\t}\n+\n+\tgraph_pad_horizontally(graph, sb);\n+\n+\t/*\n+\t * Update graph->state\n+\t */\n+\tif (graph_is_mapping_correct(graph))\n+\t\tgraph->state = GRAPH_PADDING;\n+\telse\n+\t\tgraph->state = GRAPH_COLLAPSING;\n+}\n+\n+void graph_output_collapsing_line(struct git_graph *graph, struct strbuf *sb)\n+{\n+\tint i;\n+\tint *tmp_mapping;\n+\n+\t/*\n+\t * Clear out the new_mapping array\n+\t */\n+\tfor (i = 0; i < graph->mapping_size; i++)\n+\t\tgraph->new_mapping[i] = -1;\n+\n+\tfor (i = 0; i < graph->mapping_size; i++) {\n+\t\tint target = graph->mapping[i];\n+\t\tif (target < 0)\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * Since update_columns() always inserts the leftmost\n+\t\t * column first, each branch's target location should\n+\t\t * always be either its current location or to the left of\n+\t\t * its current location.\n+\t\t *\n+\t\t * We never have to move branches to the right.  This makes\n+\t\t * the graph much more legible, since whenever branches\n+\t\t * cross, only one is moving directions.\n+\t\t */\n+\t\tassert(target * 2 <= i);\n+\n+\t\tif (target * 2 == i) {\n+\t\t\t/*\n+\t\t\t * This column is already in the\n+\t\t\t * correct place\n+\t\t\t */\n+\t\t\tassert(graph->new_mapping[i] == -1);\n+\t\t\tgraph->new_mapping[i] = target;\n+\t\t} else if (graph->new_mapping[i - 1] < 0) {\n+\t\t\t/*\n+\t\t\t * Nothing is to the left.\n+\t\t\t * Move to the left by one\n+\t\t\t */\n+\t\t\tgraph->new_mapping[i - 1] = target;\n+\t\t} else if (graph->new_mapping[i - 1] == target) {\n+\t\t\t/*\n+\t\t\t * There is a branch line to our left\n+\t\t\t * already, and it is our target.  We\n+\t\t\t * combine with this line, since we share\n+\t\t\t * the same parent commit.\n+\t\t\t *\n+\t\t\t * We don't have to add anything to the\n+\t\t\t * output or new_mapping, since the\n+\t\t\t * existing branch line has already taken\n+\t\t\t * care of it.\n+\t\t\t */\n+\t\t} else {\n+\t\t\t/*\n+\t\t\t * There is a branch line to our left,\n+\t\t\t * but it isn't our target.  We need to\n+\t\t\t * cross over it.\n+\t\t\t *\n+\t\t\t * The space just to the left of this\n+\t\t\t * branch should always be empty.\n+\t\t\t */\n+\t\t\tassert(graph->new_mapping[i - 1] > target);\n+\t\t\tassert(graph->new_mapping[i - 2] < 0);\n+\t\t\tgraph->new_mapping[i - 2] = target;\n+\t\t}\n+\t}\n+\n+\t/*\n+\t * The new mapping may be 1 smaller than the old mapping\n+\t */\n+\tif (graph->new_mapping[graph->mapping_size - 1] < 0)\n+\t\tgraph->mapping_size--;\n+\n+\t/*\n+\t * Output out a line based on the new mapping info\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\t\tstrbuf_addch(sb, ' ');\n+\t\telse if (target * 2 == i)\n+\t\t\tstrbuf_addch(sb, '|');\n+\t\telse\n+\t\t\tstrbuf_addch(sb, '/');\n+\t}\n+\n+\tgraph_pad_horizontally(graph, sb);\n+\n+\t/*\n+\t * Swap mapping and new_mapping\n+\t */\n+\ttmp_mapping = graph->mapping;\n+\tgraph->mapping = graph->new_mapping;\n+\tgraph->new_mapping = tmp_mapping;\n+\n+\t/*\n+\t * If graph->mapping indicates that all of the branch lines\n+\t * are already in the correct positions, we are done.\n+\t * Otherwise, we need to collapse some branch lines together.\n+\t */\n+\tif (graph_is_mapping_correct(graph))\n+\t\tgraph->state = GRAPH_PADDING;\n+}\n+\n+int graph_next_line(struct git_graph *graph, struct strbuf *sb)\n+{\n+\tswitch (graph->state) {\n+\tcase GRAPH_PADDING:\n+\t\tgraph_output_padding_line(graph, sb);\n+\t\treturn 0;\n+\tcase GRAPH_SKIP:\n+\t\tgraph_output_skip_line(graph, sb);\n+\t\treturn 0;\n+\tcase GRAPH_PRE_COMMIT:\n+\t\tgraph_output_pre_commit_line(graph, sb);\n+\t\treturn 0;\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+\t}\n+\n+\tassert(0);\n+\treturn 0;\n+}\n+\n+void graph_padding_line(struct git_graph *graph, struct strbuf *sb)\n+{\n+\tint i, j;\n+\n+\tif (graph->state != GRAPH_COMMIT) {\n+\t\tgraph_next_line(graph, sb);\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * Output the row containing this commit\n+\t * Iterate up to and including graph->num_columns,\n+\t * since the current commit may not be in any of the existing\n+\t * columns.  (This happens when the current commit doesn't have any\n+\t * children that we have already processed.)\n+\t */\n+\tfor (i = 0; i < graph->num_columns; i++) {\n+\t\tstruct commit *col_commit = graph->columns[i].commit;\n+\t\tif (col_commit == graph->commit) {\n+\t\t\tstrbuf_addch(sb, '|');\n+\n+\t\t\tif (graph->num_parents < 3)\n+\t\t\t\tstrbuf_addch(sb, ' ');\n+\t\t\telse {\n+\t\t\t\tint num_spaces = ((graph->num_parents - 2) * 2);\n+\t\t\t\tfor (j = 0; j < num_spaces; j++)\n+\t\t\t\t\tstrbuf_addch(sb, ' ');\n+\t\t\t}\n+\t\t} else {\n+\t\t\tstrbuf_addstr(sb, \"| \");\n+\t\t}\n+\t}\n+\n+\tgraph_pad_horizontally(graph, sb);\n+}\n+\n+int graph_is_commit_finished(struct git_graph const *graph)\n+{\n+\treturn (graph->state == GRAPH_PADDING);\n+}\n+\n+void graph_show_commit(struct git_graph *graph)\n+{\n+\tstruct strbuf msgbuf;\n+\tint shown_commit_line = 0;\n+\n+\tif (!graph)\n+\t\treturn;\n+\n+\tstrbuf_init(&msgbuf, 0);\n+\n+\twhile (!shown_commit_line) {\n+\t\tshown_commit_line = graph_next_line(graph, &msgbuf);\n+\t\tfwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);\n+\t\tif (!shown_commit_line)\n+\t\t\tputchar('\\n');\n+\t\tstrbuf_setlen(&msgbuf, 0);\n+\t}\n+\n+\tstrbuf_release(&msgbuf);\n+}\n+\n+void graph_show_oneline(struct git_graph *graph)\n+{\n+\tstruct strbuf msgbuf;\n+\n+\tif (!graph)\n+\t\treturn;\n+\n+\tstrbuf_init(&msgbuf, 0);\n+\tgraph_next_line(graph, &msgbuf);\n+\tfwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);\n+\tstrbuf_release(&msgbuf);\n+}\n+\n+void graph_show_padding(struct git_graph *graph)\n+{\n+\tstruct strbuf msgbuf;\n+\n+\tif (!graph)\n+\t\treturn;\n+\n+\tstrbuf_init(&msgbuf, 0);\n+\tgraph_padding_line(graph, &msgbuf);\n+\tfwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);\n+\tstrbuf_release(&msgbuf);\n+}\n+\n+int graph_show_remainder(struct git_graph *graph)\n+{\n+\tstruct strbuf msgbuf;\n+\tint shown = 0;\n+\n+\tif (!graph)\n+\t\treturn 0;\n+\n+\tif (graph_is_commit_finished(graph))\n+\t\treturn 0;\n+\n+\tstrbuf_init(&msgbuf, 0);\n+\tfor (;;) {\n+\t\tgraph_next_line(graph, &msgbuf);\n+\t\tfwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);\n+\t\tstrbuf_setlen(&msgbuf, 0);\n+\t\tshown = 1;\n+\n+\t\tif (!graph_is_commit_finished(graph))\n+\t\t\tputchar('\\n');\n+\t\telse\n+\t\t\tbreak;\n+\t}\n+\tstrbuf_release(&msgbuf);\n+\n+\treturn shown;\n+}\n+\n+\n+void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb)\n+{\n+\tif (!graph) {\n+\t\tfwrite(sb->buf, sizeof(char), sb->len, stdout);\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * Print the strbuf line by line,\n+\t * and display the graph info before each line but the first.\n+\t */\n+\tchar *p = sb->buf;\n+\twhile (p) {\n+\t\tsize_t len;\n+\t\tchar *next_p = strchr(p, '\\n');\n+\t\tif (next_p) {\n+\t\t\tnext_p++;\n+\t\t\tlen = next_p - p;\n+\t\t} else {\n+\t\t\tlen = (sb->buf + sb->len) - p;\n+\t\t}\n+\t\tfwrite(p, sizeof(char), len, stdout);\n+\t\tif (next_p && *next_p != '\\0')\n+\t\t\tgraph_show_oneline(graph);\n+\t\tp = next_p;\n+\t}\n+}\n+\n+void graph_show_commit_msg(struct git_graph *graph,\n+\t\t\t   struct strbuf const *sb)\n+{\n+\tif (!graph) {\n+\t\t/*\n+\t\t * If there's no graph, just print the message buffer.\n+\t\t *\n+\t\t * The message buffer for CMIT_FMT_ONELINE and\n+\t\t * CMIT_FMT_USERFORMAT are already missing a terminating\n+\t\t * newline.  All of the other formats should have it.\n+\t\t */\n+\t\tfwrite(sb->buf, sizeof(char), sb->len, stdout);\n+\t\treturn;\n+\t}\n+\n+\tint newline_terminated = (sb->len && sb->buf[sb->len - 1] == '\\n');\n+\n+\t/*\n+\t * Show the commit message\n+\t */\n+\tgraph_show_strbuf(graph, sb);\n+\n+\t/*\n+\t * If there is more output needed for this commit, show it now\n+\t */\n+\tif (!graph_is_commit_finished(graph)) {\n+\t\t/*\n+\t\t * If sb doesn't have a terminating newline, print one now,\n+\t\t * so we can start the remainder of the graph output on a\n+\t\t * new line.\n+\t\t */\n+\t\tif (!newline_terminated)\n+\t\t\tputchar('\\n');\n+\n+\t\tgraph_show_remainder(graph);\n+\n+\t\t/*\n+\t\t * If sb ends with a newline, our output should too.\n+\t\t */\n+\t\tif (newline_terminated)\n+\t\t\tputchar('\\n');\n+\t}\n+}\ndiff --git a/graph.h b/graph.h\nnew file mode 100644\nindex 0000000..a7748a5\n--- /dev/null\n+++ b/graph.h\n@@ -0,0 +1,121 @@\n+#ifndef GRAPH_H\n+#define GRAPH_H\n+\n+/* A graph is a pointer to this opaque structure */\n+struct git_graph;\n+\n+/*\n+ * Create a new struct git_graph.\n+ * The graph should be freed with graph_release() when no longer needed.\n+ */\n+struct git_graph *graph_init();\n+\n+/*\n+ * Destroy a struct git_graph and free associated memory.\n+ */\n+void graph_release(struct git_graph *graph);\n+\n+/*\n+ * Update a git_graph with a new commit.\n+ * This will cause the graph to begin outputting lines for the new commit\n+ * the next time graph_next_line() is called.\n+ *\n+ * If graph_update() is called before graph_is_commit_finished() returns 1,\n+ * the next call to graph_next_line() will output an ellipsis (\"...\")\n+ * to indicate that a portion of the graph is missing.\n+ */\n+void graph_update(struct git_graph *graph, struct commit *commit);\n+\n+/*\n+ * Output the next line for a graph.\n+ * This formats the next graph line into the specified strbuf.  It is not\n+ * terminated with a newline.\n+ *\n+ * Returns 1 if the line includes the current commit, and 0 otherwise.\n+ * graph_next_line() will return 1 exactly once for each time\n+ * graph_update() is called.\n+ */\n+int graph_next_line(struct git_graph *graph, struct strbuf *sb);\n+\n+/*\n+ * Output a padding line in the graph.\n+ * This is similar to graph_next_line().  However, it is guaranteed to\n+ * never print the current commit line.  Instead, if the commit line is\n+ * next, it will simply output a line of vertical padding, extending the\n+ * branch lines downwards, but leaving them otherwise unchanged.\n+ */\n+void graph_padding_line(struct git_graph *graph, struct strbuf *sb);\n+\n+/*\n+ * Determine if a graph has finished outputting lines for the current\n+ * commit.\n+ *\n+ * Returns 1 if graph_next_line() needs to be called again before\n+ * graph_update() should be called.  Returns 0 if no more lines are needed\n+ * for this commit.  If 0 is returned, graph_next_line() may still be\n+ * called without calling graph_update(), and it will merely output\n+ * appropriate \"vertical padding\" in the graph.\n+ */\n+int graph_is_commit_finished(struct git_graph const *graph);\n+\n+\n+/*\n+ * graph_show_*: helper functions for printing to stdout\n+ */\n+\n+\n+/*\n+ * If the graph is non-NULL, print the history graph to stdout,\n+ * up to and including the line containing this commit.\n+ * Does not print a terminating newline on the last line.\n+ */\n+void graph_show_commit(struct git_graph *graph);\n+\n+/*\n+ * If the graph is non-NULL, print one line of the history graph to stdout.\n+ * Does not print a terminating newline on the last line.\n+ */\n+void graph_show_oneline(struct git_graph *graph);\n+\n+/*\n+ * If the graph is non-NULL, print one line of vertical graph padding to\n+ * stdout.  Does not print a terminating newline on the last line.\n+ */\n+void graph_show_padding(struct git_graph *graph);\n+\n+/*\n+ * If the graph is non-NULL, print the rest of the history graph for this\n+ * commit to stdout.  Does not print a terminating newline on the last line.\n+ */\n+int graph_show_remainder(struct git_graph *graph);\n+\n+/*\n+ * Print a strbuf to stdout.  If the graph is non-NULL, all lines but the\n+ * first will be prefixed with the graph output.\n+ *\n+ * If the strbuf ends with a newline, the output will end after this\n+ * newline.  A new graph line will not be printed after the final newline.\n+ * If the strbuf is empty, no output will be printed.\n+ *\n+ * Since the first line will not include the graph ouput, the caller is\n+ * responsible for printing this line's graph (perhaps via\n+ * graph_show_commit() or graph_show_oneline()) before calling\n+ * graph_show_strbuf().\n+ */\n+void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);\n+\n+/*\n+ * Print a commit message strbuf and the remainder of the graph to stdout.\n+ *\n+ * This is similar to graph_show_strbuf(), but it always prints the\n+ * remainder of the graph.\n+ *\n+ * If the strbuf ends with a newline, the output printed by\n+ * graph_show_commit_msg() will end with a newline.  If the strbuf is\n+ * missing a terminating newline (including if it is empty), the output\n+ * printed by graph_show_commit_msg() will also be missing a terminating\n+ * newline.\n+ */\n+void graph_show_commit_msg(struct git_graph *graph, struct strbuf const *sb);\n+\n+#endif /* GRAPH_H */\n-- \n1.5.5.1.128.gc15ea\n"},{"id":"76009","messageId":"1209897414-10091-4-git-send-email-adam@adamsimpkins.net","threadId":"13369","inReplyTo":"1209897414-10091-3-git-send-email-adam@adamsimpkins.net","subject":"[PATCH 3/3] log and rev-list: add --graph option","fromName":"Adam Simpkins","fromEmail":"adam@adamsimpkins.net","sentAt":"2008-05-04T10:36:54Z","receivedAt":"2008-05-04T10:36:54Z","isPatch":true,"sender":{"key":"adam@adamsimpkins.net","avatar":"https://gravatar.com/avatar/d3fd2c0b3e2d2136b56e95726ee03227bee4eb562f627dcd3ebca0623fa05054?d=mp&s=160"},"body":"This new option causes a text-based representation of the history to be\nprinted to the left of the normal output.\n\nSigned-off-by: Adam Simpkins <adam@adamsimpkins.net>\n---\n Documentation/rev-list-options.txt            |   10 +++\n Documentation/technical/api-history-graph.txt |   13 +++--\n builtin-rev-list.c                            |   50 +++++++++++++++-\n log-tree.c                                    |   76 ++++++++++++++++++++++--\n revision.c                                    |   26 ++++++++-\n revision.h                                    |    6 ++-\n 6 files changed, 163 insertions(+), 18 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 2648a55..ce6a101 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -75,6 +75,16 @@ you would get an output line this:\n \t-xxxxxxx... 1st on a\n -----------------------------------------------------------------------\n \n+--graph::\n+\n+\tDraw a text-based graphical representation of the commit history\n+\ton the left hand side of the output.  This may cause extra lines\n+\tto be printed in between commits, in order for the graph history\n+\tto be drawn properly.\n++\n+This implies the '--topo-order' option by default, but the\n+'--date-order' option may also be specified.\n+\n Diff Formatting\n ~~~~~~~~~~~~~~~\n \ndiff --git a/Documentation/technical/api-history-graph.txt b/Documentation/technical/api-history-graph.txt\nindex 5f6465f..ce1c08e 100644\n--- a/Documentation/technical/api-history-graph.txt\n+++ b/Documentation/technical/api-history-graph.txt\n@@ -74,14 +74,17 @@ state.\n Calling sequence\n ----------------\n \n-* Create a `struct git_graph` by calling `graph_init()`.\n+* Create a `struct git_graph` by calling `graph_init()`.  When using the\n+  revision walking API, this is done automatically by `setup_revisions()` if\n+  the '--graph' option is supplied.\n \n * Use the revision walking API to walk through a group of contiguous commits.\n+  The `get_revision()` function automatically calls `graph_update()` each time\n+  it is invoked.\n \n-* For each commit traversed, call `graph_update()` to move the graph to the\n-  next commit.  Once `graph_update()` has been called, call `graph_next_line()`\n-  repeatedly, until `graph_is_commit_finished()` returns non-zero.  Each call\n-  to `graph_next_line()` will output a single line of the graph.  The resulting\n+* For each commit, call `graph_next_line()` repeatedly, until\n+  `graph_is_commit_finished()` returns non-zero.  Each call go\n+  `graph_next_line()` will output a single line of the graph.  The resulting\n   lines will not contain any newlines.  `graph_next_line()` returns 1 if the\n   resulting line contains the current commit, or 0 if this is merely a line\n   needed to adjust the graph before or after the current commit.  This return\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 476a870..f868290 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -10,6 +10,7 @@\n #include \"list-objects.h\"\n #include \"builtin.h\"\n #include \"log-tree.h\"\n+#include \"graph.h\"\n \n /* bits #0-15 in revision.h */\n \n@@ -52,12 +53,13 @@ static struct rev_info revs;\n \n static int bisect_list;\n static int show_timestamp;\n-static int hdr_termination;\n static const char *header_prefix;\n \n static void finish_commit(struct commit *commit);\n static void show_commit(struct commit *commit)\n {\n+\tgraph_show_commit(revs.graph);\n+\n \tif (show_timestamp)\n \t\tprintf(\"%lu \", commit->date);\n \tif (header_prefix)\n@@ -96,9 +98,50 @@ static void show_commit(struct commit *commit)\n \t\tpretty_print_commit(revs.commit_format, commit,\n \t\t\t\t    &buf, revs.abbrev, NULL, NULL,\n \t\t\t\t    revs.date_mode, 0);\n-\t\tif (buf.len)\n-\t\t\tprintf(\"%s%c\", buf.buf, hdr_termination);\n+\t\tif (revs.graph) {\n+\t\t\tif (buf.len) {\n+\t\t\t\tif (revs.commit_format != CMIT_FMT_ONELINE)\n+\t\t\t\t\tgraph_show_oneline(revs.graph);\n+\n+\t\t\t\tgraph_show_commit_msg(revs.graph, &buf);\n+\n+\t\t\t\t/*\n+\t\t\t\t * Add a newline after the commit message.\n+\t\t\t\t *\n+\t\t\t\t * Usually, this newline produces a blank\n+\t\t\t\t * padding line between entries, in which case\n+\t\t\t\t * we need to add graph padding on this line.\n+\t\t\t\t *\n+\t\t\t\t * However, the commit message may not end in a\n+\t\t\t\t * newline.  In this case the newline simply\n+\t\t\t\t * ends the last line of the commit message,\n+\t\t\t\t * and we don't need any graph output.  (This\n+\t\t\t\t * always happens with CMIT_FMT_ONELINE, and it\n+\t\t\t\t * happens with CMIT_FMT_USERFORMAT when the\n+\t\t\t\t * format doesn't explicitly end in a newline.)\n+\t\t\t\t */\n+\t\t\t\tif (buf.len && buf.buf[buf.len - 1] == '\\n')\n+\t\t\t\t\tgraph_show_padding(revs.graph);\n+\t\t\t\tputchar('\\n');\n+\t\t\t} else {\n+\t\t\t\t/*\n+\t\t\t\t * If the message buffer is empty, just show\n+\t\t\t\t * the rest of the graph output for this\n+\t\t\t\t * commit.\n+\t\t\t\t */\n+\t\t\t\tif (graph_show_remainder(revs.graph))\n+\t\t\t\t\tputchar('\\n');\n+\t\t\t}\n+\t\t} else {\n+\t\t\tif (buf.len) {\n+\t\t\t\tfwrite(buf.buf, sizeof(char), buf.len, stdout);\n+\t\t\t\tputchar('\\n');\n+\t\t\t}\n+\t\t}\n \t\tstrbuf_release(&buf);\n+\t} else {\n+\t\tif (graph_show_remainder(revs.graph))\n+\t\t\tputchar('\\n');\n \t}\n \tmaybe_flush_or_die(stdout, \"stdout\");\n \tfinish_commit(commit);\n@@ -592,7 +635,6 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t}\n \tif (revs.commit_format != CMIT_FMT_UNSPECIFIED) {\n \t\t/* The command line has a --pretty  */\n-\t\thdr_termination = '\\n';\n \t\tif (revs.commit_format == CMIT_FMT_ONELINE)\n \t\t\theader_prefix = \"\";\n \t\telse\ndiff --git a/log-tree.c b/log-tree.c\nindex 74829d7..1474d1f 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -1,6 +1,7 @@\n #include \"cache.h\"\n #include \"diff.h\"\n #include \"commit.h\"\n+#include \"graph.h\"\n #include \"log-tree.h\"\n #include \"reflog-walk.h\"\n \n@@ -165,11 +166,16 @@ void log_write_email_headers(struct rev_info *opt, const char *name,\n \t}\n \n \tprintf(\"From %s Mon Sep 17 00:00:00 2001\\n\", name);\n-\tif (opt->message_id)\n+\tgraph_show_oneline(opt->graph);\n+\tif (opt->message_id) {\n \t\tprintf(\"Message-Id: <%s>\\n\", opt->message_id);\n-\tif (opt->ref_message_id)\n+\t\tgraph_show_oneline(opt->graph);\n+\t}\n+\tif (opt->ref_message_id) {\n \t\tprintf(\"In-Reply-To: <%s>\\nReferences: <%s>\\n\",\n \t\t       opt->ref_message_id, opt->ref_message_id);\n+\t\tgraph_show_oneline(opt->graph);\n+\t}\n \tif (opt->mime_boundary) {\n \t\tstatic char subject_buffer[1024];\n \t\tstatic char buffer[1024];\n@@ -220,6 +226,8 @@ void show_log(struct rev_info *opt)\n \n \topt->loginfo = NULL;\n \tif (!opt->verbose_header) {\n+\t\tgraph_show_commit(opt->graph);\n+\n \t\tif (commit->object.flags & BOUNDARY)\n \t\t\tputchar('-');\n \t\telse if (commit->object.flags & UNINTERESTING)\n@@ -234,6 +242,10 @@ void show_log(struct rev_info *opt)\n \t\tif (opt->print_parents)\n \t\t\tshow_parents(commit, abbrev_commit);\n \t\tshow_decorations(commit);\n+\t\tif (opt->graph && !graph_is_commit_finished(opt->graph)) {\n+\t\t\tputchar('\\n');\n+\t\t\tgraph_show_remainder(opt->graph);\n+\t\t}\n \t\tputchar(opt->diffopt.line_termination);\n \t\treturn;\n \t}\n@@ -243,11 +255,33 @@ void show_log(struct rev_info *opt)\n \t * Otherwise, add a diffopt.line_termination character before all\n \t * entries but the first.  (IOW, as a separator between entries)\n \t */\n-\tif (opt->shown_one && !opt->use_terminator)\n+\tif (opt->shown_one && !opt->use_terminator) {\n+\t\t/*\n+\t\t * If entries are separated by a newline, the output\n+\t\t * should look human-readable.  If the last entry ended\n+\t\t * with a newline, print the graph output before this\n+\t\t * newline.  Otherwise it will end up as a completely blank\n+\t\t * line and will look like a gap in the graph.\n+\t\t *\n+\t\t * If the entry separator is not a newline, the output is\n+\t\t * primarily intended for programmatic consumption, and we\n+\t\t * never want the extra graph output before the entry\n+\t\t * separator.\n+\t\t */\n+\t\tif (opt->diffopt.line_termination == '\\n' &&\n+\t\t    !opt->missing_newline)\n+\t\t\tgraph_show_padding(opt->graph);\n \t\tputchar(opt->diffopt.line_termination);\n+\t}\n \topt->shown_one = 1;\n \n \t/*\n+\t * If the history graph was requested,\n+\t * print the graph, up to this commit's line\n+\t */\n+\tgraph_show_commit(opt->graph);\n+\n+\t/*\n \t * Print header line of header..\n \t */\n \n@@ -279,8 +313,19 @@ void show_log(struct rev_info *opt)\n \t\t\t\t\t\t  abbrev_commit));\n \t\tshow_decorations(commit);\n \t\tprintf(\"%s\", diff_get_color_opt(&opt->diffopt, DIFF_RESET));\n-\t\tputchar(opt->commit_format == CMIT_FMT_ONELINE ? ' ' : '\\n');\n+\t\tif (opt->commit_format == CMIT_FMT_ONELINE) {\n+\t\t\tputchar(' ');\n+\t\t} else {\n+\t\t\tputchar('\\n');\n+\t\t\tgraph_show_oneline(opt->graph);\n+\t\t}\n \t\tif (opt->reflog_info) {\n+\t\t\t/*\n+\t\t\t * setup_revisions() ensures that opt->reflog_info\n+\t\t\t * and opt->graph cannot both be set,\n+\t\t\t * so we don't need to worry about printing the\n+\t\t\t * graph info here.\n+\t\t\t */\n \t\t\tshow_reflog_message(opt->reflog_info,\n \t\t\t\t    opt->commit_format == CMIT_FMT_ONELINE,\n \t\t\t\t    opt->date_mode);\n@@ -304,13 +349,30 @@ void show_log(struct rev_info *opt)\n \n \tif (opt->add_signoff)\n \t\tappend_signoff(&msgbuf, opt->add_signoff);\n-\tif (opt->show_log_size)\n+\tif (opt->show_log_size) {\n \t\tprintf(\"log size %i\\n\", (int)msgbuf.len);\n+\t\tgraph_show_oneline(opt->graph);\n+\t}\n \n-\tif (msgbuf.len)\n+\t/*\n+\t * Set opt->missing_newline if msgbuf doesn't\n+\t * end in a newline (including if it is empty)\n+\t */\n+\tif (!msgbuf.len || msgbuf.buf[msgbuf.len - 1] != '\\n')\n+\t\topt->missing_newline = 1;\n+\telse\n+\t\topt->missing_newline = 0;\n+\n+\tif (opt->graph)\n+\t\tgraph_show_commit_msg(opt->graph, &msgbuf);\n+\telse\n \t\tfwrite(msgbuf.buf, sizeof(char), msgbuf.len, stdout);\n-\tif (opt->use_terminator)\n+\tif (opt->use_terminator) {\n+\t\tif (!opt->missing_newline)\n+\t\t\tgraph_show_padding(opt->graph);\n \t\tputchar('\\n');\n+\t}\n+\n \tstrbuf_release(&msgbuf);\n }\n \ndiff --git a/revision.c b/revision.c\nindex a813304..c947e0f 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -6,6 +6,7 @@\n #include \"diff.h\"\n #include \"refs.h\"\n #include \"revision.h\"\n+#include \"graph.h\"\n #include \"grep.h\"\n #include \"reflog-walk.h\"\n #include \"patch-ids.h\"\n@@ -1203,6 +1204,12 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \t\t\t\tget_commit_format(arg+8, revs);\n \t\t\t\tcontinue;\n \t\t\t}\n+\t\t\tif (!prefixcmp(arg, \"--graph\")) {\n+\t\t\t\trevs->topo_order = 1;\n+\t\t\t\trevs->rewrite_parents = 1;\n+\t\t\t\trevs->graph = graph_init();\n+\t\t\t\tcontinue;\n+\t\t\t}\n \t\t\tif (!strcmp(arg, \"--root\")) {\n \t\t\t\trevs->show_root_diff = 1;\n \t\t\t\tcontinue;\n@@ -1397,6 +1404,15 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n \tif (revs->reverse && revs->reflog_info)\n \t\tdie(\"cannot combine --reverse with --walk-reflogs\");\n \n+\t/*\n+\t * Limitations on the graph functionality\n+\t */\n+\tif (revs->reverse && revs->graph)\n+\t\tdie(\"cannot combine --reverse with --graph\");\n+\n+\tif (revs->reflog_info && revs->graph)\n+\t\tdie(\"cannot combine --walk-reflogs with --graph\");\n+\n \treturn left;\n }\n \n@@ -1598,7 +1614,7 @@ static void gc_boundary(struct object_array *array)\n \t}\n }\n \n-struct commit *get_revision(struct rev_info *revs)\n+static struct commit *get_revision_internal(struct rev_info *revs)\n {\n \tstruct commit *c = NULL;\n \tstruct commit_list *l;\n@@ -1705,3 +1721,11 @@ struct commit *get_revision(struct rev_info *revs)\n \n \treturn c;\n }\n+\n+struct commit *get_revision(struct rev_info *revs)\n+{\n+\tstruct commit *c = get_revision_internal(revs);\n+\tif (c && revs->graph)\n+\t\tgraph_update(revs->graph, c);\n+\treturn c;\n+}\ndiff --git a/revision.h b/revision.h\nindex 201bd97..abce500 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -66,7 +66,8 @@ struct rev_info {\n \t/* Format info */\n \tunsigned int\tshown_one:1,\n \t\t\tabbrev_commit:1,\n-\t\t\tuse_terminator:1;\n+\t\t\tuse_terminator:1,\n+\t\t\tmissing_newline:1;\n \tenum date_mode date_mode;\n \n \tconst char **ignore_packed; /* pretend objects in these are unpacked */\n@@ -89,6 +90,9 @@ struct rev_info {\n \t/* Filter by commit log message */\n \tstruct grep_opt\t*grep_filter;\n \n+\t/* Display history graph */\n+\tstruct git_graph *graph;\n+\n \t/* special limits */\n \tint skip_count;\n \tint max_count;\n-- \n1.5.5.1.128.gc15ea\n"},{"id":"76011","messageId":"20080504110615.GA20660@mithlond.arda.local","threadId":"13369","inReplyTo":"1209897414-10091-1-git-send-email-adam@adamsimpkins.net","subject":"[PATCH] bash: Add more option completions for 'git log'","fromName":"Teemu Likonen","fromEmail":"tlikonen@iki.fi","sentAt":"2008-05-04T11:06:15Z","receivedAt":"2008-05-04T11:06:15Z","isPatch":true,"sender":{"key":"tlikonen@iki.fi","avatar":null},"body":"Options added: --graph --stat --numstat --shortstat --decorate\n--diff-filter= --color --no-color --color-words\n\nSigned-off-by: Teemu Likonen <tlikonen@iki.fi>\n---\n\nI have found these bash completions useful with 'git log'. This patch\nalso includes the '--graph' option recently introduced by Adam Simpkins.\n\n\n contrib/completion/git-completion.bash |    4 ++++\n 1 files changed, 4 insertions(+), 0 deletions(-)\n\ndiff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash\nindex 23db664..d7a8545 100755\n--- a/contrib/completion/git-completion.bash\n+++ b/contrib/completion/git-completion.bash\n@@ -758,6 +758,10 @@ _git_log ()\n \t\t\t--pretty= --name-status --name-only --raw\n \t\t\t--not --all\n \t\t\t--left-right --cherry-pick\n+\t\t\t--stat --numstat --shortstat\n+\t\t\t--decorate --diff-filter=\n+\t\t\t--color --no-color --color-words\n+\t\t\t--graph\n \t\t\t\"\n \t\treturn\n \t\t;;\n-- \n1.5.5.1.139.g8c42a\n"},{"id":"76060","messageId":"46dff0320805041913t31c05a36w92be4a81a3da07af@mail.gmail.com","threadId":"13369","inReplyTo":"1209897414-10091-1-git-send-email-adam@adamsimpkins.net","subject":"Re: [PATCH 0/3] log --graph and rev-list --graph","fromName":"Ping Yin","fromEmail":"pkufranky@gmail.com","sentAt":"2008-05-05T02:13:43Z","receivedAt":"2008-05-05T02:13:43Z","isPatch":true,"sender":{"key":"pkufranky@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5346?v=4"},"body":"On Sun, May 4, 2008 at 6:36 PM, Adam Simpkins <adam@adamsimpkins.net> wrote:\n> This patch series adds a new --graph option to the log and rev-list\n>  commands.  This is pretty much the same code that I sent out in early\n>  April, but updated to work with the log entry termination fixes in the\n>  latest master branch.\n>\n>  Adam Simpkins (3):\n>   revision API: split parent rewriting and parent printing options\n>   Add history graph API\n>   log and rev-list: add --graph option\n>\n\nIs the indention between ba7f5b and 38254 intentional?\n\n* ba7f5b log and rev-list: add --graph option\n*   38254 Add history graph API\n*   12918 revision API: split parent rewriting\n*   c697a Cleanup xread() loops to use read_in_full()\nM     47179Merge branch 'maint'\n\n-- \nPing Yin\n"},{"id":"76076","messageId":"20080505061940.GA26319@adamsimpkins.net","threadId":"13369","inReplyTo":"46dff0320805041913t31c05a36w92be4a81a3da07af@mail.gmail.com","subject":"Re: [PATCH 0/3] log --graph and rev-list --graph","fromName":"Adam Simpkins","fromEmail":"adam@adamsimpkins.net","sentAt":"2008-05-05T06:19:41Z","receivedAt":"2008-05-05T06:19:41Z","isPatch":true,"sender":{"key":"adam@adamsimpkins.net","avatar":"https://gravatar.com/avatar/d3fd2c0b3e2d2136b56e95726ee03227bee4eb562f627dcd3ebca0623fa05054?d=mp&s=160"},"body":"On Mon, May 05, 2008 at 10:13:43AM +0800, Ping Yin wrote:\n> \n> Is the indention between ba7f5b and 38254 intentional?\n> \n> * ba7f5b log and rev-list: add --graph option\n> *   38254 Add history graph API\n> *   12918 revision API: split parent rewriting\n> *   c697a Cleanup xread() loops to use read_in_full()\n> M     47179 Merge branch 'maint'\n\n\nIt's not really intentional, it's just the result of a rather\nsimplistic computation.\n\nThe amount of horizontal padding used for each commit is computed as\n(2 * number of incoming columns from the previous commit) + (2 * number\nof parents of the current commit).  This always results in enough\npadding.  However, if the current commit is a child of one of the\nincoming columns, it results in 2 more spaces than necessary.\n\nThere's a comment in graph_pad_horizontally() graph.c that describes\nthis behavior:\n\n     * This computation results in 3 extra spaces to the right in most\n     * cases, but only 1 extra space if the commit doesn't have any\n     * children that have already been displayed in the graph (i.e.,\n     * if the current commit isn't in graph->columns).\n\nIt could easily be fixed by performing an extra pass over the columns\nto check if any of the existing columns refers to the current commit.\n\nI'll try to come up with a patch when I get the chance.\n\n-- \nAdam Simpkins\nadam@adamsimpkins.net\n"},{"id":"76081","messageId":"1209974223-2875-1-git-send-email-adam@adamsimpkins.net","threadId":"13369","inReplyTo":"1209897414-10091-4-git-send-email-adam@adamsimpkins.net","subject":"[PATCH] graph API: eliminate unnecessary indentation","fromName":"Adam Simpkins","fromEmail":"adam@adamsimpkins.net","sentAt":"2008-05-05T07:57:03Z","receivedAt":"2008-05-05T07:57:03Z","isPatch":true,"sender":{"key":"adam@adamsimpkins.net","avatar":"https://gravatar.com/avatar/d3fd2c0b3e2d2136b56e95726ee03227bee4eb562f627dcd3ebca0623fa05054?d=mp&s=160"},"body":"This change improves the calculation of the amount of horizontal\npadding, so that there is always exactly 1 space of padding.\nPreviously, most commits had 3 spaces of padding, but commits that\ndidn't have any children in the graph had only 1 space of padding.\n\nSigned-off-by: Adam Simpkins <adam@adamsimpkins.net>\n---\n\nThis fixes the issue reported by Ping Yin.\n\n graph.c |   66 +++++++++++++++++++++++++++++++++++++++++++++++++-------------\n 1 files changed, 52 insertions(+), 14 deletions(-)\n\ndiff --git a/graph.c b/graph.c\nindex b575d10..809a582 100644\n--- a/graph.c\n+++ b/graph.c\n@@ -61,6 +61,12 @@ struct git_graph {\n \t */\n \tint num_parents;\n \t/*\n+\t * The width of the graph output for this commit.\n+\t * All rows for this commit are padded to this width, so that\n+\t * messages printed after the graph output are aligned.\n+\t */\n+\tint width;\n+\t/*\n \t * The next expansion row to print\n \t * when state is GRAPH_PRE_COMMIT\n \t */\n@@ -207,13 +213,48 @@ static void graph_insert_into_new_columns(struct git_graph *graph,\n \tgraph->num_new_columns++;\n }\n \n+static void graph_update_width(struct git_graph *graph,\n+\t\t\t       int is_commit_in_existing_columns)\n+{\n+\t/*\n+\t * Compute the width needed to display the graph for this commit.\n+\t * This is the maximum width needed for any row.  All other rows\n+\t * will be padded to this width.\n+\t *\n+\t * Compute the number of columns in the widest row:\n+\t * Count each existing column (graph->num_columns), and each new\n+\t * column added by this commit.\n+\t */\n+\tint max_cols = graph->num_columns + graph->num_parents;\n+\n+\t/*\n+\t * Even if the current commit has no parents, it still takes up a\n+\t * column for itself.\n+\t */\n+\tif (graph->num_parents < 1)\n+\t\tmax_cols++;\n+\n+\t/*\n+\t * We added a column for the the current commit as part of\n+\t * graph->num_parents.  If the current commit was already in\n+\t * graph->columns, then we have double counted it.\n+\t */\n+\tif (is_commit_in_existing_columns)\n+\t\tmax_cols--;\n+\n+\t/*\n+\t * Each column takes up 2 spaces\n+\t */\n+\tgraph->width = max_cols * 2;\n+}\n+\n static void graph_update_columns(struct git_graph *graph)\n {\n \tstruct commit_list *parent;\n \tstruct column *tmp_columns;\n \tint max_new_columns;\n \tint mapping_idx;\n-\tint i, seen_this;\n+\tint i, seen_this, is_commit_in_columns;\n \n \t/*\n \t * Swap graph->columns with graph->new_columns\n@@ -259,11 +300,13 @@ static void graph_update_columns(struct git_graph *graph)\n \t */\n \tseen_this = 0;\n \tmapping_idx = 0;\n+\tis_commit_in_columns = 1;\n \tfor (i = 0; i <= graph->num_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\tis_commit_in_columns = 0;\n \t\t\tcol_commit = graph->commit;\n \t\t} else {\n \t\t\tcol_commit = graph->columns[i].commit;\n@@ -290,6 +333,11 @@ static void graph_update_columns(struct git_graph *graph)\n \twhile (graph->mapping_size > 1 &&\n \t       graph->mapping[graph->mapping_size - 1] < 0)\n \t\tgraph->mapping_size--;\n+\n+\t/*\n+\t * Compute graph->width for this commit\n+\t */\n+\tgraph_update_width(graph, is_commit_in_columns);\n }\n \n void graph_update(struct git_graph *graph, struct commit *commit)\n@@ -368,22 +416,12 @@ static void graph_pad_horizontally(struct git_graph *graph, struct strbuf *sb)\n \t *\n \t * This way, fields printed to the right of the graph will remain\n \t * aligned for the entire commit.\n-\t *\n-\t * This computation results in 3 extra space to the right in most\n-\t * cases, but only 1 extra space if the commit doesn't have any\n-\t * children that have already been displayed in the graph (i.e.,\n-\t * if the current commit isn't in graph->columns).\n \t */\n-\tsize_t extra;\n-\tsize_t final_width = graph->num_columns + graph->num_parents;\n-\tif (graph->num_parents < 1)\n-\t\tfinal_width++;\n-\tfinal_width *= 2;\n-\n-\tif (sb->len >= final_width)\n+\tint extra;\n+\tif (sb->len >= graph->width)\n \t\treturn;\n \n-\textra = final_width - sb->len;\n+\textra = graph->width - sb->len;\n \tstrbuf_addf(sb, \"%*s\", extra, \"\");\n }\n \n-- \n1.5.3.6\n"},{"id":"76112","messageId":"46dff0320805050438m44c266f4w77e23e823663be6b@mail.gmail.com","threadId":"13369","inReplyTo":"1209974223-2875-1-git-send-email-adam@adamsimpkins.net","subject":"Re: [PATCH] graph API: eliminate unnecessary indentation","fromName":"Ping Yin","fromEmail":"pkufranky@gmail.com","sentAt":"2008-05-05T11:38:38Z","receivedAt":"2008-05-05T11:38:38Z","isPatch":true,"sender":{"key":"pkufranky@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5346?v=4"},"body":"On Mon, May 5, 2008 at 3:57 PM, Adam Simpkins <adam@adamsimpkins.net> wrote:\n> This change improves the calculation of the amount of horizontal\n>  padding, so that there is always exactly 1 space of padding.\n>  Previously, most commits had 3 spaces of padding, but commits that\n>  didn't have any children in the graph had only 1 space of padding.\n>\n>  Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>\n>  ---\n>\n>  This fixes the issue reported by Ping Yin.\n>\n\nYes, this patch has fix that problem. THX.\n\n-- \nPing Yin\n"},{"id":"76181","messageId":"7vzlr4gcic.fsf@gitster.siamese.dyndns.org","threadId":"13369","inReplyTo":"1209897414-10091-3-git-send-email-adam@adamsimpkins.net","subject":"Re: [PATCH 2/3] Add history graph API","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-05-06T06:41:47Z","receivedAt":"2008-05-06T06:41:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Adam Simpkins <adam@adamsimpkins.net> writes:\n\n> +* The graph API does not currently support reverse commit ordering.  In\n> +  order to implement reverse ordering, the graphing API needs an\n> +  (efficient) mechanism to find the children of a commit.\n\nYou might want to take a look at the 'jc/blame' topic that have been\nbrewing in 'next' for the three weeks, most notably f35f560 (revision\ntraversal: --children option, 2008-04-03).\n\nThis series needs tests.\n"},{"id":"76182","messageId":"7vtzhcgci1.fsf@gitster.siamese.dyndns.org","threadId":"13369","inReplyTo":"1209897414-10091-4-git-send-email-adam@adamsimpkins.net","subject":"Re: [PATCH 3/3] log and rev-list: add --graph option","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-05-06T06:41:58Z","receivedAt":"2008-05-06T06:41:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Adam Simpkins <adam@adamsimpkins.net> writes:\n\n> diff --git a/builtin-rev-list.c b/builtin-rev-list.c\n> index 476a870..f868290 100644\n> --- a/builtin-rev-list.c\n> +++ b/builtin-rev-list.c\n> ...\n> @@ -52,12 +53,13 @@ static struct rev_info revs;\n>  \n>  static int bisect_list;\n>  static int show_timestamp;\n> -static int hdr_termination;\n>  static const char *header_prefix;\n>  \n>  static void finish_commit(struct commit *commit);\n>  static void show_commit(struct commit *commit)\n>  {\n> +\tgraph_show_commit(revs.graph);\n> +\n>  \tif (show_timestamp)\n>  \t\tprintf(\"%lu \", commit->date);\n>  \tif (header_prefix)\n> @@ -96,9 +98,50 @@ static void show_commit(struct commit *commit)\n>  \t\tpretty_print_commit(revs.commit_format, commit,\n>  \t\t\t\t    &buf, revs.abbrev, NULL, NULL,\n>  \t\t\t\t    revs.date_mode, 0);\n> -\t\tif (buf.len)\n> -\t\t\tprintf(\"%s%c\", buf.buf, hdr_termination);\n> +\t\tif (revs.graph) {\n> ...\n> +\t\t} else {\n> +\t\t\tif (buf.len) {\n> +\t\t\t\tfwrite(buf.buf, sizeof(char), buf.len, stdout);\n> +\t\t\t\tputchar('\\n');\n\nNow hdr_termination can never be NUL, iow you broke \"rev-list -v -z\"?\n\nI'll squash in a minimum fix, because otherwise this breaks existing\ntests.\n\n--\n\n builtin-rev-list.c |    8 ++++----\n 1 files changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex f868290..54d55cc 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -53,6 +53,7 @@ static struct rev_info revs;\n \n static int bisect_list;\n static int show_timestamp;\n+static int hdr_termination;\n static const char *header_prefix;\n \n static void finish_commit(struct commit *commit);\n@@ -133,10 +134,8 @@ static void show_commit(struct commit *commit)\n \t\t\t\t\tputchar('\\n');\n \t\t\t}\n \t\t} else {\n-\t\t\tif (buf.len) {\n-\t\t\t\tfwrite(buf.buf, sizeof(char), buf.len, stdout);\n-\t\t\t\tputchar('\\n');\n-\t\t\t}\n+\t\t\tif (buf.len)\n+\t\t\t\tprintf(\"%s%c\", buf.buf, hdr_termination);\n \t\t}\n \t\tstrbuf_release(&buf);\n \t} else {\n@@ -635,6 +634,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t}\n \tif (revs.commit_format != CMIT_FMT_UNSPECIFIED) {\n \t\t/* The command line has a --pretty  */\n+\t\thdr_termination = '\\n';\n \t\tif (revs.commit_format == CMIT_FMT_ONELINE)\n \t\t\theader_prefix = \"\";\n \t\telse\n"},{"id":"76184","messageId":"20080506070135.GA24803@adamsimpkins.net","threadId":"13369","inReplyTo":"7vtzhcgci1.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 3/3] log and rev-list: add --graph option","fromName":"Adam Simpkins","fromEmail":"adam@adamsimpkins.net","sentAt":"2008-05-06T07:01:36Z","receivedAt":"2008-05-06T07:01:36Z","isPatch":true,"sender":{"key":"adam@adamsimpkins.net","avatar":"https://gravatar.com/avatar/d3fd2c0b3e2d2136b56e95726ee03227bee4eb562f627dcd3ebca0623fa05054?d=mp&s=160"},"body":"On Mon, May 05, 2008 at 11:41:58PM -0700, Junio C Hamano wrote:\n> Adam Simpkins <adam@adamsimpkins.net> writes:\n> \n> > diff --git a/builtin-rev-list.c b/builtin-rev-list.c\n> > index 476a870..f868290 100644\n> > --- a/builtin-rev-list.c\n> > +++ b/builtin-rev-list.c\n> > ...\n> > @@ -96,9 +98,50 @@ static void show_commit(struct commit *commit)\n> >  \t\tpretty_print_commit(revs.commit_format, commit,\n> >  \t\t\t\t    &buf, revs.abbrev, NULL, NULL,\n> >  \t\t\t\t    revs.date_mode, 0);\n> > -\t\tif (buf.len)\n> > -\t\t\tprintf(\"%s%c\", buf.buf, hdr_termination);\n> > +\t\tif (revs.graph) {\n> > ...\n> > +\t\t} else {\n> > +\t\t\tif (buf.len) {\n> > +\t\t\t\tfwrite(buf.buf, sizeof(char), buf.len, stdout);\n> > +\t\t\t\tputchar('\\n');\n> \n> Now hdr_termination can never be NUL, iow you broke \"rev-list -v -z\"?\n\nWhoops.  Sorry about that.  I didn't notice the \"-v\" option.\n\n(BTW, I don't think the \"-z\" option comes into play here.  Just\n\"rev-list -v\" by itself results in a NUL character after each entry\ninstead of a newline.)\n\n> I'll squash in a minimum fix, because otherwise this breaks existing\n> tests.\n\nThanks!\n\n-- \nAdam Simpkins\nadam@adamsimpkins.net\n"},{"id":"76219","messageId":"20080506190305.GA19819@mithlond.arda.local","threadId":"13369","inReplyTo":"1209897414-10091-1-git-send-email-adam@adamsimpkins.net","subject":"Re: [PATCH 0/3] log --graph and rev-list --graph","fromName":"Teemu Likonen","fromEmail":"tlikonen@iki.fi","sentAt":"2008-05-06T19:03:05Z","receivedAt":"2008-05-06T19:03:05Z","isPatch":true,"sender":{"key":"tlikonen@iki.fi","avatar":null},"body":"Adam Simpkins wrote (2008-05-04 03:36 -0700):\n\n> This patch series adds a new --graph option to the log and rev-list\n> commands.  This is pretty much the same code that I sent out in early\n> April, but updated to work with the log entry termination fixes in the\n> latest master branch.\n\nLooks great, with the exception of the defects we already know: (1)\ndiff(stat) options write their output to the graph area and (2) --follow\nshows really weird lines (gitk has the same \"feature\").\n\nOther than that it seems really solid. Don't know about the code but\nfrom user's point of view:\n\nTested-by: Teemu Likonen <tlikonen@iki.fi>\n"}]}