ui-log: Implement support for commit graphs

Teach CGit to print an ASCII art commit graph to the left of the commit
message, similar to 'git log --graph'. The graph adds extra lines (table
rows) to the log when needed to add/remove/shuffle edges in the graph.

When 'showmsg' is enabled, the graph is automatically padded to account
for the extra lines added by the commit message/notes.

This feature is controlled by a new config variable: "enable-commit-graph"
(disabled by default), and individual repos can control it by setting
"repo.enable-commit-graph".

Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Lars Hjemli <hjemli@gmail.com>

6 files changed, 105 insertions, 16 deletions

diff --git a/cgit.c b/cgit.c
index 412fbf0..53ab68d 100644
--- a/cgit.c
+++ b/cgit.c
@@ -52,16 +52,18 @@ void repo_config(struct cgit_repo *repo, const char *name, const char *value)
 	else if (!strcmp(name, "desc"))
 		repo->desc = xstrdup(value);
 	else if (!strcmp(name, "owner"))
 		repo->owner = xstrdup(value);
 	else if (!strcmp(name, "defbranch"))
 		repo->defbranch = xstrdup(value);
 	else if (!strcmp(name, "snapshots"))
 		repo->snapshots = ctx.cfg.snapshots & cgit_parse_snapshots_mask(value);
+	else if (!strcmp(name, "enable-commit-graph"))
+		repo->enable_commit_graph = ctx.cfg.enable_commit_graph * atoi(value);
 	else if (!strcmp(name, "enable-log-filecount"))
 		repo->enable_log_filecount = ctx.cfg.enable_log_filecount * atoi(value);
 	else if (!strcmp(name, "enable-log-linecount"))
 		repo->enable_log_linecount = ctx.cfg.enable_log_linecount * atoi(value);
 	else if (!strcmp(name, "enable-remote-branches"))
 		repo->enable_remote_branches = atoi(value);
 	else if (!strcmp(name, "enable-subject-links"))
 		repo->enable_subject_links = atoi(value);
@@ -136,16 +138,18 @@ void config_cb(const char *name, const char *value)
 	else if (!strcmp(name, "snapshots"))
 		ctx.cfg.snapshots = cgit_parse_snapshots_mask(value);
 	else if (!strcmp(name, "enable-filter-overrides"))
 		ctx.cfg.enable_filter_overrides = atoi(value);
 	else if (!strcmp(name, "enable-gitweb-owner"))
 		ctx.cfg.enable_gitweb_owner = atoi(value);
 	else if (!strcmp(name, "enable-index-links"))
 		ctx.cfg.enable_index_links = atoi(value);
+	else if (!strcmp(name, "enable-commit-graph"))
+		ctx.cfg.enable_commit_graph = atoi(value);
 	else if (!strcmp(name, "enable-log-filecount"))
 		ctx.cfg.enable_log_filecount = atoi(value);
 	else if (!strcmp(name, "enable-log-linecount"))
 		ctx.cfg.enable_log_linecount = atoi(value);
 	else if (!strcmp(name, "enable-remote-branches"))
 		ctx.cfg.enable_remote_branches = atoi(value);
 	else if (!strcmp(name, "enable-subject-links"))
 		ctx.cfg.enable_subject_links = atoi(value);
@@ -535,16 +539,18 @@ void print_repo(FILE *f, struct cgit_repo *repo)
 	if (repo->defbranch)
 		fprintf(f, "repo.defbranch=%s\n", repo->defbranch);
 	if (repo->module_link)
 		fprintf(f, "repo.module-link=%s\n", repo->module_link);
 	if (repo->section)
 		fprintf(f, "repo.section=%s\n", repo->section);
 	if (repo->clone_url)
 		fprintf(f, "repo.clone-url=%s\n", repo->clone_url);
+	fprintf(f, "repo.enable-commit-graph=%d\n",
+	        repo->enable_commit_graph);
 	fprintf(f, "repo.enable-log-filecount=%d\n",
 	        repo->enable_log_filecount);
 	fprintf(f, "repo.enable-log-linecount=%d\n",
 	        repo->enable_log_linecount);
 	if (repo->about_filter && repo->about_filter != ctx.cfg.about_filter)
 		fprintf(f, "repo.about-filter=%s\n", repo->about_filter->cmd);
 	if (repo->commit_filter && repo->commit_filter != ctx.cfg.commit_filter)
 		fprintf(f, "repo.commit-filter=%s\n", repo->commit_filter->cmd);
diff --git a/cgit.css b/cgit.css
index 7a5f423..7600e84 100644
--- a/cgit.css
+++ b/cgit.css
@@ -148,16 +148,21 @@ table.list th {
 	vertical-align: baseline;
 }
 
 table.list td {
 	border: none;
 	padding: 0.1em 0.5em 0.1em 0.5em;
 }
 
+table.list td.commitgraph {
+	font-family: monospace;
+	white-space: pre;
+}
+
 table.list td.logsubject {
 	font-family: monospace;
 	font-weight: bold;
 }
 
 table.list td.logmsg {
 	font-family: monospace;
 	white-space: pre;
diff --git a/cgit.h b/cgit.h
index f5f68ac..bed770b 100644
--- a/cgit.h
+++ b/cgit.h
@@ -15,16 +15,17 @@
 #include <revision.h>
 #include <log-tree.h>
 #include <archive.h>
 #include <string-list.h>
 #include <xdiff-interface.h>
 #include <xdiff/xdiff.h>
 #include <utf8.h>
 #include <notes.h>
+#include <graph.h>
 
 
 /*
  * Dateformats used on misc. pages
  */
 #define FMT_LONGDATE "%Y-%m-%d %H:%M:%S (%Z)"
 #define FMT_SHORTDATE "%Y-%m-%d"
 #define FMT_ATOMDATE "%Y-%m-%dT%H:%M:%SZ"
@@ -66,16 +67,17 @@ struct cgit_repo {
 	char *desc;
 	char *owner;
 	char *defbranch;
 	char *module_link;
 	char *readme;
 	char *section;
 	char *clone_url;
 	int snapshots;
+	int enable_commit_graph;
 	int enable_log_filecount;
 	int enable_log_linecount;
 	int enable_remote_branches;
 	int enable_subject_links;
 	int max_stats;
 	time_t mtime;
 	struct cgit_filter *about_filter;
 	struct cgit_filter *commit_filter;
@@ -183,16 +185,17 @@ struct cgit_config {
 	int cache_repo_ttl;
 	int cache_root_ttl;
 	int cache_scanrc_ttl;
 	int cache_static_ttl;
 	int embedded;
 	int enable_filter_overrides;
 	int enable_gitweb_owner;
 	int enable_index_links;
+	int enable_commit_graph;
 	int enable_log_filecount;
 	int enable_log_linecount;
 	int enable_remote_branches;
 	int enable_subject_links;
 	int enable_tree_linenumbers;
 	int local_time;
 	int max_atom_items;
 	int max_repo_count;
diff --git a/cgitrc.5.txt b/cgitrc.5.txt
index 75b6584..b45c46b 100644
--- a/cgitrc.5.txt
+++ b/cgitrc.5.txt
@@ -86,16 +86,21 @@ css::
 	Url which specifies the css document to include in all cgit pages.
 	Default value: "/cgit.css".
 
 embedded::
 	Flag which, when set to "1", will make cgit generate a html fragment
 	suitable for embedding in other html pages. Default value: none. See
 	also: "noheader".
 	
+enable-commit-graph::
+	Flag which, when set to "1", will make cgit print an ASCII-art commit
+	history graph to the left of the commit messages in the repository
+	log page. Default value: "0".
+
 enable-filter-overrides::
 	Flag which, when set to "1", allows all filter settings to be
 	overridden in repository-specific cgitrc files. Default value: none.
 
 enable-gitweb-owner::
 	If set to "1" and scan-path is enabled, we first check each repository
 	for the git config value "gitweb.owner" to determine the owner.
 	Default value: "1". See also: scan-path.
@@ -349,16 +354,20 @@ repo.commit-filter::
 repo.defbranch::
 	The name of the default branch for this repository. If no such branch
 	exists in the repository, the first branch name (when sorted) is used
 	as default instead. Default value: "master".
 
 repo.desc::
 	The value to show as repository description. Default value: none.
 
+repo.enable-commit-graph::
+	A flag which can be used to disable the global setting
+	`enable-commit-graph'. Default value: none.
+
 repo.enable-log-filecount::
 	A flag which can be used to disable the global setting
 	`enable-log-filecount'. Default value: none.
 
 repo.enable-log-linecount::
 	A flag which can be used to disable the global setting
 	`enable-log-linecount'. Default value: none.
 
@@ -436,16 +445,20 @@ clone-prefix=git://foobar.com ssh://foobar.com/pub/git http://foobar.com/git
 # Specify the css url
 css=/css/cgit.css
 
 
 # Show extra links for each repository on the index page
 enable-index-links=1
 
 
+# Enable ASCII art commit history graph on the log pages
+enable-commit-graph=1
+
+
 # Show number of affected files per commit on the log pages
 enable-log-filecount=1
 
 
 # Show number of added/removed lines per commit on the log pages
 enable-log-linecount=1
 
 
diff --git a/shared.c b/shared.c
index 765cd27..7ec2e19 100644
--- a/shared.c
+++ b/shared.c
@@ -51,16 +51,17 @@ struct cgit_repo *cgit_add_repo(const char *url)
 	ret->url = trim_end(url, '/');
 	ret->name = ret->url;
 	ret->path = NULL;
 	ret->desc = "[no description]";
 	ret->owner = NULL;
 	ret->section = ctx.cfg.section;
 	ret->defbranch = "master";
 	ret->snapshots = ctx.cfg.snapshots;
+	ret->enable_commit_graph = ctx.cfg.enable_commit_graph;
 	ret->enable_log_filecount = ctx.cfg.enable_log_filecount;
 	ret->enable_log_linecount = ctx.cfg.enable_log_linecount;
 	ret->enable_remote_branches = ctx.cfg.enable_remote_branches;
 	ret->enable_subject_links = ctx.cfg.enable_subject_links;
 	ret->max_stats = ctx.cfg.max_stats;
 	ret->module_link = ctx.cfg.module_link;
 	ret->readme = ctx.cfg.readme;
 	ret->mtime = -1;
diff --git a/ui-log.c b/ui-log.c
index 6d7fcae..0d86fd5 100644
--- a/ui-log.c
+++ b/ui-log.c
@@ -72,32 +72,60 @@ void show_commit_decorations(struct commit *commit)
 			cgit_commit_link(buf, NULL, "deco", ctx.qry.head,
 					 sha1_to_hex(commit->object.sha1),
 					 ctx.qry.vpath, 0);
 		}
 		deco = deco->next;
 	}
 }
 
-void print_commit(struct commit *commit)
+void print_commit(struct commit *commit, struct rev_info *revs)
 {
 	struct commitinfo *info;
 	char *tmp;
 	int cols = 2;
+	struct strbuf graphbuf = STRBUF_INIT;
+
+	if (ctx.repo->enable_log_filecount) {
+		cols++;
+		if (ctx.repo->enable_log_linecount)
+			cols++;
+	}
+
+	if (revs->graph) {
+		/* Advance graph until current commit */
+		while (!graph_next_line(revs->graph, &graphbuf)) {
+			/* Print graph segment in otherwise empty table row */
+			html("<tr class='nohover'><td/><td class='commitgraph'>");
+			html(graphbuf.buf);
+			htmlf("</td><td colspan='%d' /></tr>\n", cols);
+			strbuf_setlen(&graphbuf, 0);
+		}
+		/* Current commit's graph segment is now ready in graphbuf */
+	}
 
 	info = cgit_parse_commit(commit);
 	htmlf("<tr%s><td>",
 		ctx.qry.showmsg ? " class='logheader'" : "");
 	tmp = fmt("id=%s", sha1_to_hex(commit->object.sha1));
 	tmp = cgit_fileurl(ctx.repo->url, "commit", ctx.qry.vpath, tmp);
 	html_link_open(tmp, NULL, NULL);
 	cgit_print_age(commit->date, TM_WEEK * 2, FMT_SHORTDATE);
 	html_link_close();
-	htmlf("</td><td%s>",
-		ctx.qry.showmsg ? " class='logsubject'" : "");
+	html("</td>");
+
+	if (revs->graph) {
+		/* Print graph segment for current commit */
+		html("<td class='commitgraph'>");
+		html(graphbuf.buf);
+		html("</td>");
+		strbuf_setlen(&graphbuf, 0);
+	}
+
+	htmlf("<td%s>", ctx.qry.showmsg ? " class='logsubject'" : "");
 	cgit_commit_link(info->subject, NULL, NULL, ctx.qry.head,
 			 sha1_to_hex(commit->object.sha1), ctx.qry.vpath, 0);
 	show_commit_decorations(commit);
 	html("</td><td>");
 	html_txt(info->author);
 	if (ctx.repo->enable_log_filecount) {
 		files = 0;
 		add_lines = 0;
@@ -107,42 +135,69 @@ void print_commit(struct commit *commit)
 		htmlf("%d", files);
 		if (ctx.repo->enable_log_linecount) {
 			html("</td><td>");
 			htmlf("-%d/+%d", rem_lines, add_lines);
 		}
 	}
 	html("</td></tr>\n");
 
-	if (ctx.qry.showmsg) { /* Print message + notes in a second table row */
-		/* Concatenate commit message and notes in msgbuf */
+	if (revs->graph || ctx.qry.showmsg) { /* Print a second table row */
 		struct strbuf msgbuf = STRBUF_INIT;
+		html("<tr class='nohover'><td/>"); /* Empty 'Age' column */
+
+		if (ctx.qry.showmsg) {
+			/* Concatenate commit message + notes in msgbuf */
 		if (info->msg && *(info->msg)) {
 			strbuf_addstr(&msgbuf, info->msg);
 			strbuf_addch(&msgbuf, '\n');
 		}
-		format_note(NULL, commit->object.sha1, &msgbuf, PAGE_ENCODING,
+			format_note(NULL, commit->object.sha1, &msgbuf,
+			            PAGE_ENCODING,
 		            NOTES_SHOW_HEADER | NOTES_INDENT);
 		strbuf_addch(&msgbuf, '\n');
 		strbuf_ltrim(&msgbuf);
+		}
 
-		if (ctx.repo->enable_log_filecount) {
-			cols++;
-			if (ctx.repo->enable_log_linecount)
-				cols++;
+		if (revs->graph) {
+			int lines = 0;
+
+			/* Calculate graph padding */
+			if (ctx.qry.showmsg) {
+				/* Count #lines in commit message + notes */
+				const char *p = msgbuf.buf;
+				lines = 1;
+				while ((p = strchr(p, '\n'))) {
+					p++;
+					lines++;
+				}
+			}
+
+			/* Print graph padding */
+			html("<td class='commitgraph'>");
+			while (lines > 0 || !graph_is_commit_finished(revs->graph)) {
+				if (graphbuf.len)
+					html("\n");
+				strbuf_setlen(&graphbuf, 0);
+				graph_next_line(revs->graph, &graphbuf);
+				html(graphbuf.buf);
+				lines--;
+			}
+			html("</td>\n");
 		}
 
-		/* Create second table row containing msgbuf */
-		htmlf("<tr class='nohover'><td/><td colspan='%d' class='logmsg'>",
-			cols);
+		/* Print msgbuf into remainder of table row */
+		htmlf("<td colspan='%d'%s>\n", cols,
+			ctx.qry.showmsg ? " class='logmsg'" : "");
 		html_txt(msgbuf.buf);
 		html("</td></tr>\n");
 		strbuf_release(&msgbuf);
 	}
 
+	strbuf_release(&graphbuf);
 	cgit_free_commitinfo(info);
 }
 
 static const char *disambiguate_ref(const char *ref)
 {
 	unsigned char sha1[20];
 	const char *longref;
 
@@ -211,16 +266,20 @@ void cgit_print_log(const char *tip, int ofs, int cnt, char *grep, char *pattern
 					fprintf(stderr, "Bad range expr: %s\n",
 						arg);
 					break;
 				}
 				vector_push(&vec, &arg, 0);
 			}
 		}
 	}
+	if (ctx.repo->enable_commit_graph) {
+		static const char *graph_arg = "--graph";
+		vector_push(&vec, &graph_arg, 0);
+	}
 
 	if (path) {
 		arg = "--";
 		vector_push(&vec, &arg, 0);
 		vector_push(&vec, &path, 0);
 	}
 
 	/* Make sure the vector is NULL-terminated */
@@ -237,18 +296,20 @@ void cgit_print_log(const char *tip, int ofs, int cnt, char *grep, char *pattern
 	rev.show_decorations = 1;
 	rev.grep_filter.regflags |= REG_ICASE;
 	compile_grep_patterns(&rev.grep_filter);
 	prepare_revision_walk(&rev);
 
 	if (pager)
 		html("<table class='list nowrap'>");
 
-	html("<tr class='nohover'><th class='left'>Age</th>"
-	      "<th class='left'>Commit message");
+	html("<tr class='nohover'><th class='left'>Age</th>");
+	if (ctx.repo->enable_commit_graph)
+		html("<th></th>");
+	html("<th class='left'>Commit message");
 	if (pager) {
 		html(" (");
 		cgit_log_link(ctx.qry.showmsg ? "Collapse" : "Expand", NULL,
 			      NULL, ctx.qry.head, ctx.qry.sha1,
 			      ctx.qry.vpath, ctx.qry.ofs, ctx.qry.grep,
 			      ctx.qry.search, ctx.qry.showmsg ? 0 : 1);
 		html(")");
 	}
@@ -269,17 +330,17 @@ void cgit_print_log(const char *tip, int ofs, int cnt, char *grep, char *pattern
 	for (i = 0; i < ofs && (commit = get_revision(&rev)) != NULL; i++) {
 		free(commit->buffer);
 		commit->buffer = NULL;
 		free_commit_list(commit->parents);
 		commit->parents = NULL;
 	}
 
 	for (i = 0; i < cnt && (commit = get_revision(&rev)) != NULL; i++) {
-		print_commit(commit);
+		print_commit(commit, &rev);
 		free(commit->buffer);
 		commit->buffer = NULL;
 		free_commit_list(commit->parents);
 		commit->parents = NULL;
 	}
 	if (pager) {
 		html("</table><div class='pager'>");
 		if (ofs > 0) {