[PATCH] Add new git-graph command

[PATCH] Add new git-graph command

[Adam Simpkins]

This is a first pass at a command to print a text-based graph of the commit
history.  It is similar to the history graph shown by gitk, but doesn't
require a windowing system.

Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
---

I added this since I really like gitk, but don't always have easy
access to an X display on some of the systems I use.  I tried using
tig, but I found its graph output very hard to read.  The graph
produced by git-graph is less compact, but much more readable.

Ultimately, it would probably be better to integrate this
functionality into git-log, instead of having it as a standalone
command.  For example, a new --graph option could be added to cause
the graph to be displayed alongside the existing git log output.
However, this would require tighter integration between the graphing
code and the log_tree.c and pretty.c code, which I'm not all that
familiar with.


 .gitignore                         |    1 +
 Documentation/git-graph.txt        |   56 ++++
 Documentation/pretty-formats.txt   |    4 +
 Documentation/rev-list-options.txt |   15 +
 Makefile                           |    1 +
 builtin-graph.c                    |  553 ++++++++++++++++++++++++++++++++++++
 builtin.h                          |    1 +
 git.c                              |    1 +
 8 files changed, 632 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/git-graph.txt
 create mode 100644 builtin-graph.c

diff --git a/.gitignore b/.gitignore
index 4ff2fec..b9b4c76 100644
--- a/.gitignore
+++ b/.gitignore
@@ -49,6 +49,7 @@ git-fsck
 git-fsck-objects
 git-gc
 git-get-tar-commit-id
+git-graph
 git-grep
 git-hash-object
 git-http-fetch
diff --git a/Documentation/git-graph.txt b/Documentation/git-graph.txt
new file mode 100644
index 0000000..022cb09
--- /dev/null
+++ b/Documentation/git-graph.txt
@@ -0,0 +1,56 @@
+git-graph(1)
+============
+
+NAME
+----
+git-graph - Show a graph of commit history
+
+
+SYNOPSIS
+--------
+'git-graph' <option>...
+
+DESCRIPTION
+-----------
+Shows a text-based representation of the commit history graph.
+
+The command takes options applicable to the linkgit:git-rev-list[1]
+command to control what is shown and how.
+
+
+OPTIONS
+-------
+
+-<n>::
+	Limits the number of commits to show.
+
+<since>..<until>::
+	Show only commits between the named two commits.  When
+	either <since> or <until> is omitted, it defaults to
+	`HEAD`, i.e. the tip of the current branch.
+	For a more complete list of ways to spell <since>
+	and <until>, see "SPECIFYING REVISIONS" section in
+	linkgit:git-rev-parse[1].
+
+:git-graph: 1
+include::rev-list-options.txt[]
+
+include::pretty-formats.txt[]
+
+
+See Also
+--------
+linkgit:gitk[1]
+
+Author
+------
+Written by Adam Simpkins <adam@adamsimpkins.net>,
+and the git list <git@vger.kernel.org>
+
+Documentation
+--------------
+Documentation by Adam Simpkins and the git list.
+
+GIT
+---
+Part of the linkgit:git[7] suite
diff --git a/Documentation/pretty-formats.txt b/Documentation/pretty-formats.txt
index 0193c3c..da76c97 100644
--- a/Documentation/pretty-formats.txt
+++ b/Documentation/pretty-formats.txt
@@ -1,6 +1,7 @@
 PRETTY FORMATS
 --------------
 
+ifndef::git-graph[]
 If the commit is a merge, and if the pretty-format
 is not 'oneline', 'email' or 'raw', an additional line is
 inserted before the 'Author:' line.  This line begins with
@@ -10,6 +11,7 @@ necessarily be the list of the *direct* parent commits if you
 have limited your view of history: for example, if you are
 only interested in changes related to a certain directory or
 file.
+endif::git-graph[]
 
 Here are some additional details for each format:
 
@@ -19,6 +21,7 @@ Here are some additional details for each format:
 +
 This is designed to be as compact as possible.
 
+ifndef::git-graph[]
 * 'short'
 
 	  commit <sha1>
@@ -75,6 +78,7 @@ displayed in full, regardless of whether --abbrev or
 --no-abbrev are used, and 'parents' information show the
 true parent commits, without taking grafts nor history
 simplification into account.
+endif::git-graph[]
 
 * 'format:'
 +
diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 2648a55..b461478 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -9,6 +9,7 @@ endif::git-rev-list[]
 
 include::pretty-options.txt[]
 
+ifndef::git-graph[]
 --relative-date::
 
 	Synonym for `--date=relative`.
@@ -37,11 +38,13 @@ format, often found in E-mail messages.
 
 	Print the contents of the commit in raw-format; each record is
 	separated with a NUL character.
+endif::git-graph[]
 
 --parents::
 
 	Print the parents of the commit.
 
+ifndef::git-graph[]
 --timestamp::
 	Print the raw commit timestamp.
 
@@ -104,6 +107,7 @@ options may be given. See linkgit:git-diff-files[1] for more options.
 -t::
 
 	Show the tree objects in the diff output. This implies '-r'.
+endif::git-graph[]
 
 Commit Limiting
 ~~~~~~~~~~~~~~~
@@ -136,6 +140,7 @@ ifdef::git-rev-list[]
 	Limit the commits output to specified time range.
 endif::git-rev-list[]
 
+ifndef::git-graph[]
 --author='pattern', --committer='pattern'::
 
 	Limit the commits output to ones with author/committer
@@ -184,6 +189,7 @@ endif::git-rev-list[]
 	adjusting to updated upstream from time to time, and
 	this option allows you to ignore the individual commits
 	brought in to your history by such a merge.
+endif::git-graph[]
 
 --not::
 
@@ -195,6 +201,7 @@ endif::git-rev-list[]
 	Pretend as if all the refs in `$GIT_DIR/refs/` are listed on the
 	command line as '<commit>'.
 
+ifndef::git-graph[]
 --stdin::
 
 	In addition to the '<commit>' listed on the command
@@ -260,6 +267,7 @@ merges that do not touch the given paths.
 Use the '--sparse' flag to makes the command output all eligible commits
 (still subject to count and age limitation), but apply merge
 simplification nevertheless.
+endif::git-graph[]
 
 ifdef::git-rev-list[]
 --bisect::
@@ -316,7 +324,12 @@ endif::git-rev-list[]
 Commit Ordering
 ~~~~~~~~~~~~~~~
 
+ifndef::git-graph[]
 By default, the commits are shown in reverse chronological order.
+endif::git-graph[]
+ifdef::git-graph[]
+By default, the commits are shown in topological order.
+endif::git-graph[]
 
 --topo-order::
 
@@ -329,6 +342,7 @@ By default, the commits are shown in reverse chronological order.
 	parent comes before all of its children, but otherwise things
 	are still ordered in the commit timestamp order.
 
+ifndef::git-graph[]
 --reverse::
 
 	Output the commits in reverse order.
@@ -366,3 +380,4 @@ These options are mostly targeted for packing of git repositories.
 --do-walk::
 
 	Overrides a previous --no-walk.
+endif::git-graph[]
diff --git a/Makefile b/Makefile
index 7c70b00..da4ce9d 100644
--- a/Makefile
+++ b/Makefile
@@ -495,6 +495,7 @@ BUILTIN_OBJS += builtin-fmt-merge-msg.o
 BUILTIN_OBJS += builtin-for-each-ref.o
 BUILTIN_OBJS += builtin-fsck.o
 BUILTIN_OBJS += builtin-gc.o
+BUILTIN_OBJS += builtin-graph.o
 BUILTIN_OBJS += builtin-grep.o
 BUILTIN_OBJS += builtin-init-db.o
 BUILTIN_OBJS += builtin-log.o
diff --git a/builtin-graph.c b/builtin-graph.c
new file mode 100644
index 0000000..1b8be2c
--- /dev/null
+++ b/builtin-graph.c
@@ -0,0 +1,553 @@
+/*
+ * Builtin "git graph"
+ */
+#include "cache.h"
+#include "color.h"
+#include "commit.h"
+#include "diff.h"
+#include "log-tree.h"
+#include "revision.h"
+
+/*
+ * TODO:
+ * - Add colors to the graph.
+ *   Pick a color for each column, and print all characters
+ *   in that column with the specified color.
+ *
+ * - Limit the number of columns, similar to the way gitk does.
+ *   If we reach more than a specified number of columns, omit
+ *   sections of some columns.
+ *
+ * - Get rid of some unnecessary memory allocations.
+ *   graph_commit() allocates new_columns, mapping, and new_mapping each
+ *   time it is called.  These could be stored in the struct graph, and
+ *   re-used each time.  They only need to be re-allocated if the number
+ *   of columns grows too big.  (If we place a limit on the max number of
+ *   columns to be displayed, we may never need to reallocate them.)
+ *
+ * - It would be nice to support other --pretty formats.
+ *   Currently things don't work well if print_commit_info() prints
+ *   multiple lines.  However, we could make it always prefix the output
+ *   with the right characters.  It wouldn't be too hard to prefix it with
+ *   the correct branch lines, using "|" characters (we could hijack
+ *   opts->diffopt.line_termination).  It would be nicer if we could get it
+ *   to work so that the extra info was printed along side the
+ *   "branch collapsing" phase.
+ *
+ * - Perhaps this entire command could just be merged into git-log.
+ *   It would certainly be nicer if git-log just had a --graph option that
+ *   caused the output to be prefixed by the graph.  This would require
+ *   the graphing code be integrated with the log-tree.c and pretty.c code.
+ */
+
+struct column {
+	/*
+	 * The parent commit of this column.
+	 */
+	struct commit *commit;
+	/*
+	 * XXX: Once we add support for colors, struct column could also
+	 * contain the color of its branch line.
+	 */
+};
+
+struct graph {
+	int num_columns;
+	struct column *columns;
+};
+
+static void update_columns(struct commit *commit,
+			  struct column *columns,
+			  int *num_columns,
+			  int *mapping,
+			  int mapping_index)
+{
+	int i;
+
+	/*
+	 * If the commit is already in the columns list, we don't need to
+	 * add it.  Just update the mapping correctly.
+	 */
+	for (i = 0; i < *num_columns; ++i) {
+		if (columns[i].commit == commit) {
+			mapping[mapping_index] = i;
+			return;
+		}
+	}
+
+	/*
+	 * This commit isn't already in columns.  Add it.
+	 */
+	columns[*num_columns].commit = commit;
+	mapping[mapping_index] = *num_columns;
+	++*num_columns;
+}
+
+static int is_mapping_correct(int const *mapping, int mapping_size)
+{
+	int i;
+
+	/*
+	 * The mapping is up to date if each entry is at its target,
+	 * or is 1 greater than its target.
+	 * (If it is 1 greater than the target, '/' will be printed, so it
+	 * will look correct on the next row.)
+	 */
+	for (i = 0; i < mapping_size; ++i) {
+		int target = mapping[i];
+		if (target < 0)
+			continue;
+		if (target == (i / 2))
+			continue;
+		return 0;
+	}
+
+	return 1;
+}
+
+static void draw_pre_commit_rows(struct rev_info *opts,
+				 struct commit *commit,
+				 struct graph *graph,
+				 int num_parents)
+{
+    int num_expansion_rows;
+    int i, j, seen_this;
+
+    /*
+     * If there are less than 3 parents, we don't need to do anything.
+     * We can immediately draw the commit line.
+     */
+    if (num_parents < 3)
+	return;
+
+    /*
+     * This commit has more than 2 parents, so we need to expand the
+     * branch lines around it to allow more room for it.
+     *
+     * We need 2 extra rows for every parent over 2
+     */
+    num_expansion_rows = (num_parents - 2) * 2;
+    for (i = 0; i < num_expansion_rows; ++i) {
+	seen_this = 0;
+	for (j = 0; j < graph->num_columns; ++j) {
+	    struct column *col = &graph->columns[j];
+	    if (col->commit == commit) {
+		seen_this = 1;
+		printf("| %*s", i, "");
+	    } else if (seen_this) {
+		printf("\\ ");
+	    } else {
+		printf("| ");
+	    }
+	}
+	printf("\n");
+    }
+}
+
+static void print_commit_info(struct rev_info *opts, struct commit *commit)
+{
+	log_tree_commit(opts, commit);
+
+	/*
+	 * log_tree_commit doesn't quite do what we want with respect to
+	 * newlines.  Unless CMIT_FMT_ONELINE is being used, it wants to
+	 * print the newline just before each log message, instead of after
+	 * it.  Manually print the line terminator, and stop
+	 * log_tree_commit() from printing one the next time it is called.
+	 */
+	if (opts->commit_format != CMIT_FMT_ONELINE)
+	{
+		putchar(opts->diffopt.line_termination);
+		opts->shown_one = 0;
+	}
+}
+
+static void draw_commit_row(struct rev_info *opts,
+			    struct commit *commit,
+			    struct graph *graph,
+			    int num_parents)
+{
+    int seen_this = 0;
+    int i, j;
+
+    /*
+     * Print the row containing this commit
+     */
+    seen_this = 0;
+    for (i = 0; i <= graph->num_columns; ++i) {
+	struct commit *col_commit;
+	if (i == graph->num_columns) {
+	    if (seen_this)
+		break;
+	    col_commit = commit;
+	} else {
+	    col_commit = graph->columns[i].commit;
+	}
+
+	if (col_commit == commit) {
+	    seen_this = 1;
+	    if (num_parents > 1)
+		putchar('M');
+	    else
+		putchar('*');
+
+	    if (num_parents < 2)
+		putchar(' ');
+	    else if (num_parents == 2)
+		printf("  ");
+	    else {
+		int num_dashes = ((num_parents - 2) * 2) - 1;
+		for (j = 0; j < num_dashes; ++j)
+		    putchar('-');
+		putchar('.');
+		putchar(' ');
+	    }
+	} else if (seen_this && (num_parents > 1)) {
+	    printf("\\ ");
+	} else {
+	    printf("| ");
+	}
+    }
+
+    /*
+     * Print the commit description.
+     * This will include a newline.
+     */
+    print_commit_info(opts, commit);
+}
+
+static void draw_post_commit_row(struct rev_info *opts,
+				 struct commit *commit,
+				 struct graph *graph,
+				 int num_parents)
+{
+    int seen_this = 0;
+    int i, j;
+
+    /*
+     * Unless this is a merge commit, we don't have anything to do
+     */
+    if (num_parents < 2)
+	return;
+
+    /*
+     * For merge commits, we need 1 additional row after the commit
+     * row to straighten out the branch lines
+     */
+    for (i = 0; i <= graph->num_columns; ++i) {
+	struct commit *col_commit;
+	if (i == graph->num_columns) {
+	    if (seen_this)
+		break;
+	    col_commit = commit;
+	} else {
+	    col_commit = graph->columns[i].commit;
+	}
+
+	if (col_commit == commit) {
+	    seen_this = 1;
+	    putchar('|');
+	    for (j = 0; j < num_parents - 1; ++j)
+		printf("\\ ");
+	    if (num_parents == 2)
+		putchar(' ');
+	} else if (seen_this && (num_parents > 2)) {
+	    printf("\\ ");
+	} else {
+	    printf("| ");
+	}
+    }
+    putchar('\n');
+}
+
+static void graph_commit(struct rev_info *opts, struct commit *commit,
+			  struct graph *graph)
+{
+	struct commit_list *parent;
+	int num_parents = 0;
+	int seen_this = 0;
+	int i;
+	int num_new_columns, max_new_columns;
+	struct column *new_columns;
+	int *mapping;
+	int *new_mapping;
+	int mapping_size, mapping_idx;
+
+	/*
+	 * Count how many parents this commit has
+	 */
+	for (parent = commit->parents; parent; parent = parent->next)
+		++num_parents;
+
+	draw_pre_commit_rows(opts, commit, graph, num_parents);
+	draw_commit_row(opts, commit, graph, num_parents);
+	draw_post_commit_row(opts, commit, graph, num_parents);
+
+	/*
+	 * Allocate room for the updated column info.
+	 * At most, there will be graph->num_columns + num_parents
+	 * columns for the next commit.
+	 *
+	 * XXX: We could avoid this allocation.  We really only need 2
+	 * column arrays, and we can swap between them each time
+	 * graph_commit() is called.
+	 */
+	max_new_columns = graph->num_columns + num_parents;
+	new_columns = xmalloc(sizeof(struct column) * max_new_columns);
+
+	mapping_size = max_new_columns * 2;
+	mapping = xmalloc(sizeof(int) * mapping_size);
+	new_mapping = xmalloc(sizeof(int) * mapping_size);
+	for (i = 0; i < mapping_size; ++i)
+		mapping[i] = -1;
+
+	/*
+	 * Some of the parents of this commit may already be in
+	 * graph->columns.  If so, we need to collapse them with the
+	 * existing branch lines.
+	 */
+	num_new_columns = 0;
+	seen_this = 0;
+	mapping_idx = 0;
+	for (i = 0; i <= graph->num_columns; ++i) {
+		struct commit *col_commit;
+		if (i == graph->num_columns) {
+			if (seen_this)
+				break;
+			col_commit = commit;
+		} else {
+			col_commit = graph->columns[i].commit;
+		}
+
+		if (col_commit == commit) {
+			seen_this = 1;
+			for (parent = commit->parents;
+			     parent;
+			     parent = parent->next) {
+				update_columns(parent->item, new_columns,
+					       &num_new_columns, mapping,
+					       mapping_idx);
+				mapping_idx += 2;
+			}
+		} else {
+			update_columns(col_commit, new_columns,
+				       &num_new_columns, mapping, mapping_idx);
+			mapping_idx += 2;
+		}
+	}
+
+	/*
+	 * Shrink mapping_size to be the minimum necessary
+	 */
+	while (mapping_size > 1 && mapping[mapping_size - 1] < 0)
+		--mapping_size;
+
+	/*
+	 * mapping now indicates a mapping between incoming branch lines
+	 * and which column they need to go to.
+	 *
+	 * Print lines to match the branch lines up to the correct column.
+	 */
+	while (!is_mapping_correct(mapping, mapping_size))
+	{
+		int *tmp_mapping;
+
+		for (i = 0; i < mapping_size; ++i)
+			new_mapping[i] = -1;
+
+		for (i = 0; i < mapping_size; ++i) {
+			int target = mapping[i];
+			if (target < 0)
+				continue;
+
+			/*
+			 * Since update_columns() always inserts the
+			 * leftmost column first, each branch's target
+			 * location should always be either its current
+			 * location or to the left of its current location.
+			 *
+			 * We never have to move branches to the right.
+			 * This makes the graph much more legible, since
+			 * whenever branches cross, only one is moving
+			 * directions.
+			 */
+			assert(target * 2 <= i);
+
+			if (target * 2 == i) {
+				/*
+				 * This column is already in the
+				 * correct place
+				 */
+				assert(new_mapping[i] == -1);
+				new_mapping[i] = target;
+			} else if (new_mapping[i - 1] < 0) {
+				/*
+				 * Nothing is to the left.
+				 * Move to the left by one
+				 */
+				new_mapping[i - 1] = target;
+			} else if (new_mapping[i - 1] == target) {
+				/*
+				 * There is a branch line to our left
+				 * already, and it is our target.  We
+				 * combine with this line, since we share
+				 * the same parent commit.
+				 *
+				 * We don't have to add anything to the
+				 * output or new_mapping, since the
+				 * existing branch line has already taken
+				 * care of it.
+				 */
+			} else {
+				/*
+				 * There is a branch line to our left,
+				 * but it isn't our target.  We need to
+				 * cross over it.
+				 *
+				 * The space just to the left of this
+				 * branch should always be empty.
+				 */
+				assert(new_mapping[i - 1] > target);
+				assert(new_mapping[i - 2] < 0);
+				new_mapping[i - 2] = target;
+			}
+		}
+
+		/*
+		 * The new mapping may be 1 smaller than the old mapping
+		 */
+		if (new_mapping[mapping_size - 1] < 0)
+			--mapping_size;
+
+		/*
+		 * Print out a line based on the new mapping info
+		 */
+		for (i = 0; i < mapping_size; ++i) {
+			int target = new_mapping[i];
+			if (target < 0)
+				putchar(' ');
+			else if (target * 2 == i)
+				putchar('|');
+			else
+				putchar('/');
+		}
+		putchar('\n');
+
+		/*
+		 * Swap mapping and new_mapping
+		 */
+		tmp_mapping = mapping;
+		mapping = new_mapping;
+		new_mapping = tmp_mapping;
+	}
+
+	/*
+	 * Update the graph with the new branch line info.
+	 */
+	graph->num_columns = num_new_columns;
+	free(graph->columns);
+	graph->columns = new_columns;
+
+	free(mapping);
+	free(new_mapping);
+}
+
+static int cmd_graph_walk(struct rev_info *opts)
+{
+	struct commit *commit;
+
+	struct graph graph;
+	graph.num_columns = 0;
+	graph.columns = NULL;
+
+	/*
+	 * XXX: Should we handle opts->early_output?
+	 */
+
+	if (prepare_revision_walk(opts))
+		die("revision walk setup failed");
+
+	/*
+	 * Walk through the commits.
+	 *
+	 * XXX: This only works if the commits form a contiguous group.
+	 * graph_commit() expects to see all commits in a particular chain.
+	 * If intervening commits are left out, it doesn't work
+	 * properly--it can't detect the parent-child relationships, and
+	 * incorrectly displays commits with missing children as the tip of
+	 * a new branch.  For example, this happens when you run
+	 * "git graph <path>".
+	 */
+	while ((commit = get_revision(opts)) != NULL) {
+		graph_commit(opts, commit, &graph);
+	}
+
+	return 0;
+}
+
+static void cmd_graph_init(int ac, const char **av, const char *prefix,
+			   struct rev_info *opts)
+{
+	int i;
+
+	git_config(git_diff_ui_config);
+	if (diff_use_color_default == -1)
+		diff_use_color_default = git_use_color_default;
+
+	init_revisions(opts, prefix);
+
+	opts->always_show_header = 1;
+	opts->abbrev = DEFAULT_ABBREV;
+	opts->topo_order = 1;
+	opts->commit_format = CMIT_FMT_ONELINE;
+	opts->verbose_header = 1;
+
+	/*
+	 * XXX: We don't really want to allow all of the options
+	 * that setup_revisions() parses.  In particular, most of the
+	 * diff-related options don't apply to us.
+	 */
+	ac = setup_revisions(ac, av, opts, "HEAD");
+
+	/*
+	 * XXX: At the moment, we can't handle --reverse
+	 */
+	if (opts->reverse)
+		die("--reverse is unsupported");
+
+	/*
+	 * Only CMIT_FMT_ONELINE and CMIT_FMT_USERFORMAT make sense,
+	 * since the commit info needs to be on a single line.
+	 *
+	 * XXX: It would be nice to have access to cmt_fmts from pretty.c,
+	 * so we could print the name of the unsupported format.
+	 */
+	if (opts->commit_format != CMIT_FMT_ONELINE &&
+	    opts->commit_format != CMIT_FMT_USERFORMAT)
+		die("--pretty must be oneline or format");
+
+	/*
+	 * We don't handle first_parent_only yet.
+	 * (It isn't too hard to implement, but it doesn't seem terribly
+	 * useful.)
+	 */
+	if (opts->first_parent_only)
+	    die("--first-parent is not implemented for git-graph");
+
+	/*
+	 * Handle remaining arguments.
+	 * Eventually we may support other options here.
+	 */
+	for (i = 1; i < ac; i++) {
+		const char *arg = av[i];
+		die("unrecognized argument: %s", arg);
+	}
+}
+
+int cmd_graph(int ac, const char **av, const char *prefix)
+{
+	struct rev_info opts;
+
+	cmd_graph_init(ac, av, prefix, &opts);
+	return cmd_graph_walk(&opts);
+}
diff --git a/builtin.h b/builtin.h
index 95126fd..1801993 100644
--- a/builtin.h
+++ b/builtin.h
@@ -43,6 +43,7 @@ extern int cmd_format_patch(int argc, const char **argv, const char *prefix);
 extern int cmd_fsck(int argc, const char **argv, const char *prefix);
 extern int cmd_gc(int argc, const char **argv, const char *prefix);
 extern int cmd_get_tar_commit_id(int argc, const char **argv, const char *prefix);
+extern int cmd_graph(int argc, const char **argv, const char *prefix);
 extern int cmd_grep(int argc, const char **argv, const char *prefix);
 extern int cmd_help(int argc, const char **argv, const char *prefix);
 extern int cmd_http_fetch(int argc, const char **argv, const char *prefix);
diff --git a/git.c b/git.c
index b7729d7..9d5fd09 100644
--- a/git.c
+++ b/git.c
@@ -306,6 +306,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "fsck-objects", cmd_fsck, RUN_SETUP },
 		{ "gc", cmd_gc, RUN_SETUP },
 		{ "get-tar-commit-id", cmd_get_tar_commit_id },
+		{ "graph", cmd_graph, RUN_SETUP | USE_PAGER },
 		{ "grep", cmd_grep, RUN_SETUP | USE_PAGER },
 		{ "help", cmd_help },
 #ifndef NO_CURL
-- 
1.5.5.rc2.1.ge6b5a.dirty

Re: [PATCH] Add new git-graph command

[Jakub Narebski]

Adam Simpkins <adam@adamsimpkins.net> writes:

> This is a first pass at a command to print a text-based graph of the commit
> history.  It is similar to the history graph shown by gitk, but doesn't
> require a windowing system.

Should I understand that git-show-branch has too cryptic an output?

-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: [PATCH] Add new git-graph command

[Adam Simpkins]

On Sun, Mar 30, 2008 at 01:41:43PM -0700, Jakub Narebski wrote:
> Adam Simpkins <adam@adamsimpkins.net> writes:
> 
> > This is a first pass at a command to print a text-based graph of the commit
> > history.  It is similar to the history graph shown by gitk, but doesn't
> > require a windowing system.
> 
> Should I understand that git-show-branch has too cryptic an output?

Yes, I find it a bit hard to read with more than just a few branches.

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH] Add new git-graph command

[Matthieu Moy]

Adam Simpkins <adam@adamsimpkins.net> writes:

> This is a first pass at a command to print a text-based graph of the commit
> history.  It is similar to the history graph shown by gitk, but doesn't
> require a windowing system.

Did you look at git-forest too?

http://git.or.cz/gitwiki/InterfacesFrontendsAndTools#head-ed34e1966c28f24d459c5ad30a21457baa9bed23

-- 
Matthieu

Re: [PATCH] Add new git-graph command

[Adam Simpkins]

On Sun, Mar 30, 2008 at 10:44:29PM +0200, Matthieu Moy wrote:
> Adam Simpkins <adam@adamsimpkins.net> writes:
> 
> > This is a first pass at a command to print a text-based graph of the commit
> > history.  It is similar to the history graph shown by gitk, but doesn't
> > require a windowing system.
> 
> Did you look at git-forest too?
> 
> http://git.or.cz/gitwiki/InterfacesFrontendsAndTools#head-ed34e1966c28f24d459c5ad30a21457baa9bed23

Interesting, I wasn't aware of this utility.  It does look very
similar.

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH] Add new git-graph command

[Johannes Schindelin]

Hi,

On Sun, 30 Mar 2008, Adam Simpkins wrote:

> This is a first pass at a command to print a text-based graph of the 
> commit history.  It is similar to the history graph shown by gitk, but 
> doesn't require a windowing system.
> 
> Signed-off-by: Adam Simpkins <adam@adamsimpkins.net>
> ---
> 
> I added this since I really like gitk, but don't always have easy access 
> to an X display on some of the systems I use.  I tried using tig, but I 
> found its graph output very hard to read.  The graph produced by 
> git-graph is less compact, but much more readable.
> 
> Ultimately, it would probably be better to integrate this functionality 
> into git-log, instead of having it as a standalone command.  For 
> example, a new --graph option could be added to cause the graph to be 
> displayed alongside the existing git log output. However, this would 
> require tighter integration between the graphing code and the log_tree.c 
> and pretty.c code, which I'm not all that familiar with.

Funny.  Some time ago, Shawn and I mused how involved it would be to write 
some tool very similar to this, only that the output could be read back by 
git-gui.  This would be needed for a sensible "rebase -i" implementation 
in git-gui.

Ciao,
Dscho

Re: [PATCH] Add new git-graph command

[Junio C Hamano]

What's wrong with "tig -g", I have to wonder...

Re: [PATCH] Add new git-graph command

[Adam Simpkins]

On Sun, Mar 30, 2008 at 04:49:16PM -0700, Junio C Hamano wrote:
> What's wrong with "tig -g", I have to wonder...

As I mentioned in my initial email, I tried using the graph in tig,
but I found it very hard to read.  However, going back and taking a
closer look at tig, I think its graph is just plain wrong in some
cases.

For example, here's a comparison of the first several lines of output
of "git-graph --date-order --all" and "tig -- --all" in my repository
for one of the projects I am working on.  I've replaced the commit
subjects with just the abbreviated hashes.  (Hopefully your mail
reader displays this with a monospace font.)

git-graph:

*   8076867
*   2613e2b
M    542f526
|\  
* |   642b381
| | *   e73dfa2
| \ \ 
|  \ \ 
M-. \ \   64e1d85
|\ \ \ \ 
| | * | |   836521f
| | | | | *   ce43181
| | | | | *   eaeeb08
| | | | | M    79d3db3
| | | | | |\  
| | | | | | *   da5bc9e
| * | | | | |   b947aab
| | | | | M  \   9ade1bc
| | | | | |\  | 
| | | | * | | |   8f3727b
| | | | * | | |   2d102cd
* | | | | | | |   bf5c6e3
| |/ / / / / / 
|/| / / / / / 
* | | | | | |   a570370
|/ / / / / / 
* | | | | |   dde9a00
| | | | | *   09048ce
| | | | |/ 
| | | | *   4ee2351



tig (version 0.10.git):

+ 8076867
* 2613e2b
M 542f526
* | 642b381
| | + e73dfa2
M |  \ \ 64e1d85
|`.`* | | 836521f
| | | | | + ce43181
| | | | | * eaeeb08
| | | | | M 79d3db3
| | | | | |`* da5bc9e
| * | | | | | b947aab
| | | | | M  \ 9ade1bc
| | | | * |`.`. 8f3727b
| | | | * | | | 2d102cd
* | | | | | | | bf5c6e3
*' / / / / / / a570370
*' / / / / / dde9a00
| | | | | * 09048ce
| | | | *' 4ee2351


Looking at the tig output, it seems like tig is definitely screwing up
around the 3-way merge at 64e1d85.  The way I read the output, it
looks like it is telling me that commit 836521f is a parent of
542f526, which is incorrect.

It also doesn't seem to display things correctly when branch lines
need to cross.  For example, 836521f is a child of a570370, and
b947aab is a child of dde9a00.  However, the way I read tig's graph,
it looks like it is telling me exactly the opposite--that 836521f is a
child of dde9a00 and b947aab is a child of a570370.

I think part of the problem is that tig displays exactly 1 commit per
line.  It's hard to represent octopus merges and crossing branches if
it all has to fit in 1 line.  This is why git-graph sometimes takes
extra lines in between commits to display where the branch lines are
going.

The git-forest command that Matthieu Moy pointed out also seems to do
a good job of representing the graph, while being a bit more compact
than git-graph when displaying crossing branches.  (I just joined the
list in the last couple of days, so I wasn't aware of git-forest.  I
did try googling for similar tools before I started, but only came up
with tig.)

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH] Add new git-graph command

[Teemu Likonen]

Adam Simpkins kirjoitti:

> I added this since I really like gitk, but don't always have easy
> access to an X display on some of the systems I use.  I tried using
> tig, but I found its graph output very hard to read.  The graph
> produced by git-graph is less compact, but much more readable.
>
> Ultimately, it would probably be better to integrate this
> functionality into git-log, instead of having it as a standalone
> command.  For example, a new --graph option could be added to cause
> the graph to be displayed alongside the existing git log output.
> However, this would require tighter integration between the graphing
> code and the log_tree.c and pretty.c code, which I'm not all that
> familiar with.

I just want to say that I really like your 'git graph'. I would like to 
see it integrated to 'git log', perhaps as 'git log --pretty=graph' 
or 'git log --graph'.

Re: [PATCH] Add new git-graph command

[Adam Simpkins]

On Mon, Mar 31, 2008 at 08:17:28PM +0300, Teemu Likonen wrote:
> Adam Simpkins kirjoitti:
> 
> > Ultimately, it would probably be better to integrate this
> > functionality into git-log, instead of having it as a standalone
> > command.  For example, a new --graph option could be added to cause
> > the graph to be displayed alongside the existing git log output.
> > However, this would require tighter integration between the graphing
> > code and the log_tree.c and pretty.c code, which I'm not all that
> > familiar with.
> 
> I just want to say that I really like your 'git graph'. I would like to 
> see it integrated to 'git log', perhaps as 'git log --pretty=graph' 
> or 'git log --graph'.

Thanks!

I was thinking more about how to add it to 'git log', and it might not
be all that difficult.  Instead of providing the graphing
functionality as a standalone command, it could be wrapped up in the
following API:

  struct graph;
  void graph_update(struct graph *graph, struct commit *commit);
  void graph_next_line(struct graph *graph, struct strbuf *sb);
  bool graph_is_commit_finished(struct graph *graph);

While walking through the commit list, graph_update() should be called
once for each commit.  After graph_update() has been called,
graph_next_line() can then be called to format the next line of the
graph into the strbuf.  It should be called multiple times, until
graph_is_commit_finished() returns true.  Then graph_update() can be
called with the next commit.

If graph_next_line() is called when graph_is_commit_finished()
returns, it would simply format straight lines for each column.  For
example, if there were currently 3 columns, it would format "| | |".
This allows graph_next_line() to be used to vertically pad the graph.

This API would allow the 'git log' code to format each line of the
graph into a strbuf, and print it out in front of each line of normal
log output.  This way, it could work even with something like
"git log --graph --pretty=full".  The graph would be prefixed to the
normal output, and padded vertically for as long as necessary.

I'm just not sure how difficult it will be to change the log-tree.c
code to invoke graph_next_line() before each individual line of
output.  It certainly shouldn't be that difficult just to implement
'git log --pretty=graph', but it may be more complicated if we want to
make the graphing be a boolean option that can be enabled with any
--pretty format.

I might try coding it up next weekend.

-- 
Adam Simpkins
adam@adamsimpkins.net

Re: [PATCH] Add new git-graph command

[Stephen Sinclair]

On Mon, Mar 31, 2008 at 1:17 PM, Teemu Likonen <tlikonen@iki.fi> wrote:
>  I just want to say that I really like your 'git graph'. I would like to
>  see it integrated to 'git log', perhaps as 'git log --pretty=graph'
>  or 'git log --graph'.

Any reason?

I don't see why it's necessary to bundle all useful commands into one
big super-command.  I like the idea of typing "git-graph".
Then again, I happen to like the git-command syntax which seems to
have fallen out of favour, so don't pay attention to me.


Steve

Re: [PATCH] Add new git-graph command

[Teemu Likonen]

Stephen Sinclair kirjoitti:

> On Mon, Mar 31, 2008 at 1:17 PM, Teemu Likonen <tlikonen@iki.fi> 
wrote:
> >  I just want to say that I really like your 'git graph'. I would
> > like to see it integrated to 'git log', perhaps as 'git log
> > --pretty=graph' or 'git log --graph'.
>
> Any reason?
>
> I don't see why it's necessary to bundle all useful commands into one
> big super-command.  I like the idea of typing "git-graph".
> Then again, I happen to like the git-command syntax which seems to
> have fallen out of favour, so don't pay attention to me.

Adam's 'git graph' is a way of viewing log (in terminal environment), it 
looks very similar to 'git log --pretty=oneline' and it accepts very 
much the same command line options. That's why I see 'git log' being 
logical place for such functionality.

Actually, to me it would be more logical if 'git whatchanged' was 'git 
log --changed' or '--verbose / -v' something.

Re: [PATCH] Add new git-graph command

[Jeff King]

On Tue, Apr 01, 2008 at 07:29:51AM +0300, Teemu Likonen wrote:

> Adam's 'git graph' is a way of viewing log (in terminal environment), it 
> looks very similar to 'git log --pretty=oneline' and it accepts very 
> much the same command line options. That's why I see 'git log' being 
> logical place for such functionality.

Adam suggested that it may be possible to abstract the graphing API so
that it can be called progressively. I would love to see:

  git log --pretty=format:'%g %h %s'

where %g would be "the graph lines for this commit." But maybe that is
not workable since the graph may take multiple lines to show.

> Actually, to me it would be more logical if 'git whatchanged' was 'git 
> log --changed' or '--verbose / -v' something.

How about:

  git log --raw --full-history --always

which is identical. Though in most cases, one would be happy with "git
log --raw". I think whatchanged really only exists separately because it
predates the merging of many of the revision-walking commands.

-Peff

Re: [PATCH] Add new git-graph command

[Teemu Likonen]

Teemu Likonen kirjoitti:

> Adam's 'git graph' is a way of viewing log (in terminal environment),
> it looks very similar to 'git log --pretty=oneline' and it accepts
> very much the same command line options. That's why I see 'git log'
> being logical place for such functionality.
>
> Actually, to me it would be more logical if 'git whatchanged' was
> 'git log --changed' or '--verbose / -v' something.

May I add that I'm the kind of user who only understands the porcelain 
Git. In my mindset it's best when commands are in logical units by 
their functionality (from user's point of view).

I see 'git log' as a command for studying history log and to me 'git 
whatchanged' sounds like some user's personal _alias_ to 'git 
log --raw --full-history --always' or something (thanks Jeff). 
Similarly 'git graph' sounds like an alias to 'git log --pretty=graph' 
for someone who uses this a lot.