Merge branch 'maint' into tj/imap-send-remove-unused

* maint: (18123 commits)
  documentation fix: git difftool uses diff tools, not merge tools.
  Git 1.7.7.4
  Makefile: add missing header file dependencies
  notes merge: eliminate OUTPUT macro
  mailmap: xcalloc mailmap_info
  name-rev --all: do not even attempt to describe non-commit object
  Git 1.7.7.3
  docs: Update install-doc-quick
  docs: don't mention --quiet or --exit-code in git-log(1)
  Git 1.7.7.2
  t7511: avoid use of reserved filename on Windows.
  clone: Quote user supplied path in a single quote pair
  read-cache.c: fix index memory allocation
  make the sample pre-commit hook script reject names with newlines, too
  Reindent closing bracket using tab instead of spaces
  Git 1.7.7.1
  RelNotes/1.7.7.1: setgid bit patch is about fixing "git init" via Makefile setting
  gitweb: fix regression when filtering out forks
  Almost ready for 1.7.7.1
  pack-objects: don't traverse objects unnecessarily
  ...

Conflicts:
	imap-send.c

1 files changed, 614 insertions, 405 deletions

diff --git a/commit.c b/commit.c
index 06d543915..9f4cc636d 100644
--- a/commit.c
+++ b/commit.c
@@ -1,54 +1,24 @@
 #include "cache.h"
 #include "tag.h"
 #include "commit.h"
+#include "pkt-line.h"
+#include "utf8.h"
+#include "diff.h"
+#include "revision.h"
+#include "notes.h"
 
 int save_commit_buffer = 1;
 
-struct sort_node
-{
-	/*
-         * the number of children of the associated commit
-         * that also occur in the list being sorted.
-         */
-	unsigned int indegree;
-
-	/*
-         * reference to original list item that we will re-use
-         * on output.
-         */
-	struct commit_list * list_item;
-
-};
-
 const char *commit_type = "commit";
 
-enum cmit_fmt get_commit_format(const char *arg)
-{
-	if (!*arg)
-		return CMIT_FMT_DEFAULT;
-	if (!strcmp(arg, "=raw"))
-		return CMIT_FMT_RAW;
-	if (!strcmp(arg, "=medium"))
-		return CMIT_FMT_MEDIUM;
-	if (!strcmp(arg, "=short"))
-		return CMIT_FMT_SHORT;
-	if (!strcmp(arg, "=full"))
-		return CMIT_FMT_FULL;
-	if (!strcmp(arg, "=fuller"))
-		return CMIT_FMT_FULLER;
-	if (!strcmp(arg, "=oneline"))
-		return CMIT_FMT_ONELINE;
-	die("invalid --pretty format");
-}
-
 static struct commit *check_commit(struct object *obj,
 				   const unsigned char *sha1,
 				   int quiet)
 {
-	if (obj->type != commit_type) {
+	if (obj->type != OBJ_COMMIT) {
 		if (!quiet)
 			error("Object %s is a %s, not a commit",
-			      sha1_to_hex(sha1), obj->type);
+			      sha1_to_hex(sha1), typename(obj->type));
 		return NULL;
 	}
 	return (struct commit *) obj;
@@ -69,44 +39,69 @@ struct commit *lookup_commit_reference(const unsigned char *sha1)
 	return lookup_commit_reference_gently(sha1, 0);
 }
 
+struct commit *lookup_commit_or_die(const unsigned char *sha1, const char *ref_name)
+{
+	struct commit *c = lookup_commit_reference(sha1);
+	if (!c)
+		die(_("could not parse %s"), ref_name);
+	if (hashcmp(sha1, c->object.sha1)) {
+		warning(_("%s %s is not a commit!"),
+			ref_name, sha1_to_hex(sha1));
+	}
+	return c;
+}
+
 struct commit *lookup_commit(const unsigned char *sha1)
 {
 	struct object *obj = lookup_object(sha1);
-	if (!obj) {
-		struct commit *ret = xmalloc(sizeof(struct commit));
-		memset(ret, 0, sizeof(struct commit));
-		created_object(sha1, &ret->object);
-		ret->object.type = commit_type;
-		return ret;
-	}
+	if (!obj)
+		return create_object(sha1, OBJ_COMMIT, alloc_commit_node());
 	if (!obj->type)
-		obj->type = commit_type;
+		obj->type = OBJ_COMMIT;
 	return check_commit(obj, sha1, 0);
 }
 
-static unsigned long parse_commit_date(const char *buf)
+struct commit *lookup_commit_reference_by_name(const char *name)
+{
+	unsigned char sha1[20];
+	struct commit *commit;
+
+	if (get_sha1(name, sha1))
+		return NULL;
+	commit = lookup_commit_reference(sha1);
+	if (!commit || parse_commit(commit))
+		return NULL;
+	return commit;
+}
+
+static unsigned long parse_commit_date(const char *buf, const char *tail)
 {
-	unsigned long date;
+	const char *dateptr;
 
+	if (buf + 6 >= tail)
+		return 0;
 	if (memcmp(buf, "author", 6))
 		return 0;
-	while (*buf++ != '\n')
+	while (buf < tail && *buf++ != '\n')
 		/* nada */;
+	if (buf + 9 >= tail)
+		return 0;
 	if (memcmp(buf, "committer", 9))
 		return 0;
-	while (*buf++ != '>')
+	while (buf < tail && *buf++ != '>')
+		/* nada */;
+	if (buf >= tail)
+		return 0;
+	dateptr = buf;
+	while (buf < tail && *buf++ != '\n')
 		/* nada */;
-	date = strtoul(buf, NULL, 10);
-	if (date == ULONG_MAX)
-		date = 0;
-	return date;
+	if (buf >= tail)
+		return 0;
+	/* dateptr < buf && buf[-1] == '\n', so strtoul will stop at buf-1 */
+	return strtoul(dateptr, NULL, 10);
 }
 
-static struct commit_graft {
-	unsigned char sha1[20];
-	int nr_parent;
-	unsigned char parent[0][20]; /* more */
-} **commit_graft;
+static struct commit_graft **commit_graft;
 static int commit_graft_alloc, commit_graft_nr;
 
 static int commit_graft_pos(const unsigned char *sha1)
@@ -117,7 +112,7 @@ static int commit_graft_pos(const unsigned char *sha1)
 	while (lo < hi) {
 		int mi = (lo + hi) / 2;
 		struct commit_graft *graft = commit_graft[mi];
-		int cmp = memcmp(sha1, graft->sha1, 20);
+		int cmp = hashcmp(sha1, graft->sha1);
 		if (!cmp)
 			return mi;
 		if (cmp < 0)
@@ -128,112 +123,169 @@ static int commit_graft_pos(const unsigned char *sha1)
 	return -lo - 1;
 }
 
-static void prepare_commit_graft(void)
+int register_commit_graft(struct commit_graft *graft, int ignore_dups)
+{
+	int pos = commit_graft_pos(graft->sha1);
+
+	if (0 <= pos) {
+		if (ignore_dups)
+			free(graft);
+		else {
+			free(commit_graft[pos]);
+			commit_graft[pos] = graft;
+		}
+		return 1;
+	}
+	pos = -pos - 1;
+	if (commit_graft_alloc <= ++commit_graft_nr) {
+		commit_graft_alloc = alloc_nr(commit_graft_alloc);
+		commit_graft = xrealloc(commit_graft,
+					sizeof(*commit_graft) *
+					commit_graft_alloc);
+	}
+	if (pos < commit_graft_nr)
+		memmove(commit_graft + pos + 1,
+			commit_graft + pos,
+			(commit_graft_nr - pos - 1) *
+			sizeof(*commit_graft));
+	commit_graft[pos] = graft;
+	return 0;
+}
+
+struct commit_graft *read_graft_line(char *buf, int len)
+{
+	/* The format is just "Commit Parent1 Parent2 ...\n" */
+	int i;
+	struct commit_graft *graft = NULL;
+
+	while (len && isspace(buf[len-1]))
+		buf[--len] = '\0';
+	if (buf[0] == '#' || buf[0] == '\0')
+		return NULL;
+	if ((len + 1) % 41)
+		goto bad_graft_data;
+	i = (len + 1) / 41 - 1;
+	graft = xmalloc(sizeof(*graft) + 20 * i);
+	graft->nr_parent = i;
+	if (get_sha1_hex(buf, graft->sha1))
+		goto bad_graft_data;
+	for (i = 40; i < len; i += 41) {
+		if (buf[i] != ' ')
+			goto bad_graft_data;
+		if (get_sha1_hex(buf + i + 1, graft->parent[i/41]))
+			goto bad_graft_data;
+	}
+	return graft;
+
+bad_graft_data:
+	error("bad graft data: %s", buf);
+	free(graft);
+	return NULL;
+}
+
+static int read_graft_file(const char *graft_file)
 {
-	char *graft_file = get_graft_file();
 	FILE *fp = fopen(graft_file, "r");
 	char buf[1024];
-	if (!fp) {
-		commit_graft = (struct commit_graft **) "hack";
-		return;
-	}
+	if (!fp)
+		return -1;
 	while (fgets(buf, sizeof(buf), fp)) {
 		/* The format is just "Commit Parent1 Parent2 ...\n" */
 		int len = strlen(buf);
-		int i;
-		struct commit_graft *graft = NULL;
-
-		if (buf[len-1] == '\n')
-			buf[--len] = 0;
-		if (buf[0] == '#')
-			continue;
-		if ((len + 1) % 41) {
-		bad_graft_data:
-			error("bad graft data: %s", buf);
-			free(graft);
+		struct commit_graft *graft = read_graft_line(buf, len);
+		if (!graft)
 			continue;
-		}
-		i = (len + 1) / 41 - 1;
-		graft = xmalloc(sizeof(*graft) + 20 * i);
-		graft->nr_parent = i;
-		if (get_sha1_hex(buf, graft->sha1))
-			goto bad_graft_data;
-		for (i = 40; i < len; i += 41) {
-			if (buf[i] != ' ')
-				goto bad_graft_data;
-			if (get_sha1_hex(buf + i + 1, graft->parent[i/41]))
-				goto bad_graft_data;
-		}
-		i = commit_graft_pos(graft->sha1);
-		if (0 <= i) {
+		if (register_commit_graft(graft, 1))
 			error("duplicate graft data: %s", buf);
-			free(graft);
-			continue;
-		}
-		i = -i - 1;
-		if (commit_graft_alloc <= ++commit_graft_nr) {
-			commit_graft_alloc = alloc_nr(commit_graft_alloc);
-			commit_graft = xrealloc(commit_graft,
-						sizeof(*commit_graft) *
-						commit_graft_alloc);
-		}
-		if (i < commit_graft_nr)
-			memmove(commit_graft + i + 1,
-				commit_graft + i,
-				(commit_graft_nr - i - 1) *
-				sizeof(*commit_graft));
-		commit_graft[i] = graft;
 	}
 	fclose(fp);
+	return 0;
 }
 
-static struct commit_graft *lookup_commit_graft(const unsigned char *sha1)
+static void prepare_commit_graft(void)
+{
+	static int commit_graft_prepared;
+	char *graft_file;
+
+	if (commit_graft_prepared)
+		return;
+	graft_file = get_graft_file();
+	read_graft_file(graft_file);
+	/* make sure shallows are read */
+	is_repository_shallow();
+	commit_graft_prepared = 1;
+}
+
+struct commit_graft *lookup_commit_graft(const unsigned char *sha1)
 {
 	int pos;
-	if (!commit_graft)
-		prepare_commit_graft();
+	prepare_commit_graft();
 	pos = commit_graft_pos(sha1);
 	if (pos < 0)
 		return NULL;
 	return commit_graft[pos];
 }
 
-int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)
+int for_each_commit_graft(each_commit_graft_fn fn, void *cb_data)
+{
+	int i, ret;
+	for (i = ret = 0; i < commit_graft_nr && !ret; i++)
+		ret = fn(commit_graft[i], cb_data);
+	return ret;
+}
+
+int unregister_shallow(const unsigned char *sha1)
+{
+	int pos = commit_graft_pos(sha1);
+	if (pos < 0)
+		return -1;
+	if (pos + 1 < commit_graft_nr)
+		memmove(commit_graft + pos, commit_graft + pos + 1,
+				sizeof(struct commit_graft *)
+				* (commit_graft_nr - pos - 1));
+	commit_graft_nr--;
+	return 0;
+}
+
+int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size)
 {
-	char *bufptr = buffer;
+	const char *tail = buffer;
+	const char *bufptr = buffer;
 	unsigned char parent[20];
 	struct commit_list **pptr;
 	struct commit_graft *graft;
-	unsigned n_refs = 0;
 
 	if (item->object.parsed)
 		return 0;
 	item->object.parsed = 1;
-	if (memcmp(bufptr, "tree ", 5))
+	tail += size;
+	if (tail <= bufptr + 46 || memcmp(bufptr, "tree ", 5) || bufptr[45] != '\n')
 		return error("bogus commit object %s", sha1_to_hex(item->object.sha1));
 	if (get_sha1_hex(bufptr + 5, parent) < 0)
 		return error("bad tree pointer in commit %s",
 			     sha1_to_hex(item->object.sha1));
 	item->tree = lookup_tree(parent);
-	if (item->tree)
-		n_refs++;
 	bufptr += 46; /* "tree " + "hex sha1" + "\n" */
 	pptr = &item->parents;
 
 	graft = lookup_commit_graft(item->object.sha1);
-	while (!memcmp(bufptr, "parent ", 7)) {
+	while (bufptr + 48 < tail && !memcmp(bufptr, "parent ", 7)) {
 		struct commit *new_parent;
 
-		if (get_sha1_hex(bufptr + 7, parent) || bufptr[47] != '\n')
+		if (tail <= bufptr + 48 ||
+		    get_sha1_hex(bufptr + 7, parent) ||
+		    bufptr[47] != '\n')
 			return error("bad parents in commit %s", sha1_to_hex(item->object.sha1));
 		bufptr += 48;
-		if (graft)
+		/*
+		 * The clone is shallow if nr_parent < 0, and we must
+		 * not traverse its real parents even when we unhide them.
+		 */
+		if (graft && (graft->nr_parent < 0 || grafts_replace_parents))
 			continue;
 		new_parent = lookup_commit(parent);
-		if (new_parent) {
+		if (new_parent)
 			pptr = &commit_list_insert(new_parent, pptr)->next;
-			n_refs++;
-		}
 	}
 	if (graft) {
 		int i;
@@ -243,39 +295,29 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)
 			if (!new_parent)
 				continue;
 			pptr = &commit_list_insert(new_parent, pptr)->next;
-			n_refs++;
 		}
 	}
-	item->date = parse_commit_date(bufptr);
-
-	if (track_object_refs) {
-		unsigned i = 0;
-		struct commit_list *p;
-		struct object_refs *refs = alloc_object_refs(n_refs);
-		if (item->tree)
-			refs->ref[i++] = &item->tree->object;
-		for (p = item->parents; p; p = p->next)
-			refs->ref[i++] = &p->item->object;
-		set_object_refs(&item->object, refs);
-	}
+	item->date = parse_commit_date(bufptr, tail);
 
 	return 0;
 }
 
 int parse_commit(struct commit *item)
 {
-	char type[20];
+	enum object_type type;
 	void *buffer;
 	unsigned long size;
 	int ret;
 
+	if (!item)
+		return -1;
 	if (item->object.parsed)
 		return 0;
-	buffer = read_sha1_file(item->object.sha1, type, &size);
+	buffer = read_sha1_file(item->object.sha1, &type, &size);
 	if (!buffer)
 		return error("Could not read %s",
 			     sha1_to_hex(item->object.sha1));
-	if (strcmp(type, commit_type)) {
+	if (type != OBJ_COMMIT) {
 		free(buffer);
 		return error("Object %s not a commit",
 			     sha1_to_hex(item->object.sha1));
@@ -289,6 +331,25 @@ int parse_commit(struct commit *item)
 	return ret;
 }
 
+int find_commit_subject(const char *commit_buffer, const char **subject)
+{
+	const char *eol;
+	const char *p = commit_buffer;
+
+	while (*p && (*p != '\n' || p[1] != '\n'))
+		p++;
+	if (*p) {
+		p += 2;
+		for (eol = p; *eol && *eol != '\n'; eol++)
+			; /* do nothing */
+	} else
+		eol = p;
+
+	*subject = p;
+
+	return eol - p;
+}
+
 struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)
 {
 	struct commit_list *new_list = xmalloc(sizeof(struct commit_list));
@@ -298,6 +359,14 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list *
 	return new_list;
 }
 
+unsigned commit_list_count(const struct commit_list *l)
+{
+	unsigned c = 0;
+	for (; l; l = l->next )
+		c++;
+	return c;
+}
+
 void free_commit_list(struct commit_list *list)
 {
 	while (list) {
@@ -307,7 +376,7 @@ void free_commit_list(struct commit_list *list)
 	}
 }
 
-struct commit_list * insert_by_date(struct commit *item, struct commit_list **list)
+struct commit_list * commit_list_insert_by_date(struct commit *item, struct commit_list **list)
 {
 	struct commit_list **pp = list;
 	struct commit_list *p;
@@ -320,12 +389,12 @@ struct commit_list * insert_by_date(struct commit *item, struct commit_list **li
 	return commit_list_insert(item, pp);
 }
 
-	
-void sort_by_date(struct commit_list **list)
+
+void commit_list_sort_by_date(struct commit_list **list)
 {
 	struct commit_list *ret = NULL;
 	while (*list) {
-		insert_by_date((*list)->item, &ret);
+		commit_list_insert_by_date((*list)->item, &ret);
 		*list = (*list)->next;
 	}
 	*list = ret;
@@ -343,10 +412,9 @@ struct commit *pop_most_recent_commit(struct commit_list **list,
 
 	while (parents) {
 		struct commit *commit = parents->item;
-		parse_commit(commit);
-		if (!(commit->object.flags & mark)) {
+		if (!parse_commit(commit) && !(commit->object.flags & mark)) {
 			commit->object.flags |= mark;
-			insert_by_date(commit, list);
+			commit_list_insert_by_date(commit, list);
 		}
 		parents = parents->next;
 	}
@@ -355,319 +423,460 @@ struct commit *pop_most_recent_commit(struct commit_list **list,
 
 void clear_commit_marks(struct commit *commit, unsigned int mark)
 {
-	struct commit_list *parents;
+	while (commit) {
+		struct commit_list *parents;
 
-	parents = commit->parents;
-	commit->object.flags &= ~mark;
-	while (parents) {
-		struct commit *parent = parents->item;
-		if (parent && parent->object.parsed &&
-		    (parent->object.flags & mark))
-			clear_commit_marks(parent, mark);
-		parents = parents->next;
+		if (!(mark & commit->object.flags))
+			return;
+
+		commit->object.flags &= ~mark;
+
+		parents = commit->parents;
+		if (!parents)
+			return;
+
+		while ((parents = parents->next))
+			clear_commit_marks(parents->item, mark);
+
+		commit = commit->parents->item;
 	}
 }
 
-/*
- * Generic support for pretty-printing the header
- */
-static int get_one_line(const char *msg, unsigned long len)
+struct commit *pop_commit(struct commit_list **stack)
 {
-	int ret = 0;
+	struct commit_list *top = *stack;
+	struct commit *item = top ? top->item : NULL;
 
-	while (len--) {
-		char c = *msg++;
-		ret++;
-		if (c == '\n')
-			break;
-		if (!c)
-			return 0;
+	if (top) {
+		*stack = top->next;
+		free(top);
 	}
-	return ret;
+	return item;
 }
 
-static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const char *line)
+/*
+ * Performs an in-place topological sort on the list supplied.
+ */
+void sort_in_topological_order(struct commit_list ** list, int lifo)
 {
-	char *date;
-	int namelen;
-	unsigned long time;
-	int tz, ret;
-	const char *filler = "    ";
+	struct commit_list *next, *orig = *list;
+	struct commit_list *work, **insert;
+	struct commit_list **pptr;
 
-	if (fmt == CMIT_FMT_ONELINE)
-		return 0;
-	date = strchr(line, '>');
-	if (!date)
-		return 0;
-	namelen = ++date - line;
-	time = strtoul(date, &date, 10);
-	tz = strtol(date, NULL, 10);
-
-	ret = sprintf(buf, "%s: %.*s%.*s\n", what,
-		      (fmt == CMIT_FMT_FULLER) ? 4 : 0,
-		      filler, namelen, line);
-	switch (fmt) {
-	case CMIT_FMT_MEDIUM:
-		ret += sprintf(buf + ret, "Date:   %s\n", show_date(time, tz));
-		break;
-	case CMIT_FMT_FULLER:
-		ret += sprintf(buf + ret, "%sDate: %s\n", what, show_date(time, tz));
-		break;
-	default:
-		/* notin' */
-		break;
+	if (!orig)
+		return;
+	*list = NULL;
+
+	/* Mark them and clear the indegree */
+	for (next = orig; next; next = next->next) {
+		struct commit *commit = next->item;
+		commit->indegree = 1;
 	}
-	return ret;
-}
 
-static int is_empty_line(const char *line, int len)
-{
-	while (len && isspace(line[len-1]))
-		len--;
-	return !len;
-}
+	/* update the indegree */
+	for (next = orig; next; next = next->next) {
+		struct commit_list * parents = next->item->parents;
+		while (parents) {
+			struct commit *parent = parents->item;
 
-static int add_merge_info(enum cmit_fmt fmt, char *buf, const struct commit *commit, int abbrev)
-{
-	struct commit_list *parent = commit->parents;
-	int offset;
+			if (parent->indegree)
+				parent->indegree++;
+			parents = parents->next;
+		}
+	}
 
-	if ((fmt == CMIT_FMT_ONELINE) || !parent || !parent->next)
-		return 0;
+	/*
+	 * find the tips
+	 *
+	 * tips are nodes not reachable from any other node in the list
+	 *
+	 * the tips serve as a starting set for the work queue.
+	 */
+	work = NULL;
+	insert = &work;
+	for (next = orig; next; next = next->next) {
+		struct commit *commit = next->item;
+
+		if (commit->indegree == 1)
+			insert = &commit_list_insert(commit, insert)->next;
+	}
+
+	/* process the list in topological order */
+	if (!lifo)
+		commit_list_sort_by_date(&work);
 
-	offset = sprintf(buf, "Merge:");
+	pptr = list;
+	*list = NULL;
+	while (work) {
+		struct commit *commit;
+		struct commit_list *parents, *work_item;
+
+		work_item = work;
+		work = work_item->next;
+		work_item->next = NULL;
 
-	while (parent) {
-		struct commit *p = parent->item;
-		const char *hex = abbrev
-			? find_unique_abbrev(p->object.sha1, abbrev)
-			: sha1_to_hex(p->object.sha1);
-		char *dots = (abbrev && strlen(hex) != 40) ? "..." : "";
-		parent = parent->next;
+		commit = work_item->item;
+		for (parents = commit->parents; parents ; parents = parents->next) {
+			struct commit *parent = parents->item;
+
+			if (!parent->indegree)
+				continue;
 
-		offset += sprintf(buf + offset, " %s%s", hex, dots);
+			/*
+			 * parents are only enqueued for emission
+			 * when all their children have been emitted thereby
+			 * guaranteeing topological order.
+			 */
+			if (--parent->indegree == 1) {
+				if (!lifo)
+					commit_list_insert_by_date(parent, &work);
+				else
+					commit_list_insert(parent, &work);
+			}
+		}
+		/*
+		 * work_item is a commit all of whose children
+		 * have already been emitted. we can emit it now.
+		 */
+		commit->indegree = 0;
+		*pptr = work_item;
+		pptr = &work_item->next;
 	}
-	buf[offset++] = '\n';
-	return offset;
 }
 
-unsigned long pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit, unsigned long len, char *buf, unsigned long space, int abbrev)
+/* merge-base stuff */
+
+/* bits #0..15 in revision.h */
+#define PARENT1		(1u<<16)
+#define PARENT2		(1u<<17)
+#define STALE		(1u<<18)
+#define RESULT		(1u<<19)
+
+static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
+
+static struct commit *interesting(struct commit_list *list)
 {
-	int hdr = 1, body = 0;
-	unsigned long offset = 0;
-	int indent = (fmt == CMIT_FMT_ONELINE) ? 0 : 4;
-	int parents_shown = 0;
-	const char *msg = commit->buffer;
+	while (list) {
+		struct commit *commit = list->item;
+		list = list->next;
+		if (commit->object.flags & STALE)
+			continue;
+		return commit;
+	}
+	return NULL;
+}
 
-	for (;;) {
-		const char *line = msg;
-		int linelen = get_one_line(msg, len);
+static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
+{
+	struct commit_list *list = NULL;
+	struct commit_list *result = NULL;
+	int i;
 
-		if (!linelen)
-			break;
+	for (i = 0; i < n; i++) {
+		if (one == twos[i])
+			/*
+			 * We do not mark this even with RESULT so we do not
+			 * have to clean it up.
+			 */
+			return commit_list_insert(one, &result);
+	}
 
-		/*
-		 * We want some slop for indentation and a possible
-		 * final "...". Thus the "+ 20".
-		 */
-		if (offset + linelen + 20 > space) {
-			memcpy(buf + offset, "    ...\n", 8);
-			offset += 8;
-			break;
-		}
+	if (parse_commit(one))
+		return NULL;
+	for (i = 0; i < n; i++) {
+		if (parse_commit(twos[i]))
+			return NULL;
+	}
 
-		msg += linelen;
-		len -= linelen;
-		if (hdr) {
-			if (linelen == 1) {
-				hdr = 0;
-				if (fmt != CMIT_FMT_ONELINE)
-					buf[offset++] = '\n';
-				continue;
-			}
-			if (fmt == CMIT_FMT_RAW) {
-				memcpy(buf + offset, line, linelen);
-				offset += linelen;
-				continue;
+	one->object.flags |= PARENT1;
+	commit_list_insert_by_date(one, &list);
+	for (i = 0; i < n; i++) {
+		twos[i]->object.flags |= PARENT2;
+		commit_list_insert_by_date(twos[i], &list);
+	}
+
+	while (interesting(list)) {
+		struct commit *commit;
+		struct commit_list *parents;
+		struct commit_list *next;
+		int flags;
+
+		commit = list->item;
+		next = list->next;
+		free(list);
+		list = next;
+
+		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
+		if (flags == (PARENT1 | PARENT2)) {
+			if (!(commit->object.flags & RESULT)) {
+				commit->object.flags |= RESULT;
+				commit_list_insert_by_date(commit, &result);
 			}
-			if (!memcmp(line, "parent ", 7)) {
-				if (linelen != 48)
-					die("bad parent line in commit");
+			/* Mark parents of a found merge stale */
+			flags |= STALE;
+		}
+		parents = commit->parents;
+		while (parents) {
+			struct commit *p = parents->item;
+			parents = parents->next;
+			if ((p->object.flags & flags) == flags)
 				continue;
-			}
+			if (parse_commit(p))
+				return NULL;
+			p->object.flags |= flags;
+			commit_list_insert_by_date(p, &list);
+		}
+	}
 
-			if (!parents_shown) {
-				offset += add_merge_info(fmt, buf + offset,
-							 commit, abbrev);
-				parents_shown = 1;
-				continue;
+	/* Clean up the result to remove stale ones */
+	free_commit_list(list);
+	list = result; result = NULL;
+	while (list) {
+		struct commit_list *next = list->next;
+		if (!(list->item->object.flags & STALE))
+			commit_list_insert_by_date(list->item, &result);
+		free(list);
+		list = next;
+	}
+	return result;
+}
+
+struct commit_list *get_octopus_merge_bases(struct commit_list *in)
+{
+	struct commit_list *i, *j, *k, *ret = NULL;
+	struct commit_list **pptr = &ret;
+
+	for (i = in; i; i = i->next) {
+		if (!ret)
+			pptr = &commit_list_insert(i->item, pptr)->next;
+		else {
+			struct commit_list *new = NULL, *end = NULL;
+
+			for (j = ret; j; j = j->next) {
+				struct commit_list *bases;
+				bases = get_merge_bases(i->item, j->item, 1);
+				if (!new)
+					new = bases;
+				else
+					end->next = bases;
+				for (k = bases; k; k = k->next)
+					end = k;
 			}
-			/*
-			 * MEDIUM == DEFAULT shows only author with dates.
-			 * FULL shows both authors but not dates.
-			 * FULLER shows both authors and dates.
-			 */
-			if (!memcmp(line, "author ", 7))
-				offset += add_user_info("Author", fmt,
-							buf + offset,
-							line + 7);
-			if (!memcmp(line, "committer ", 10) &&
-			    (fmt == CMIT_FMT_FULL || fmt == CMIT_FMT_FULLER))
-				offset += add_user_info("Commit", fmt,
-							buf + offset,
-							line + 10);
-			continue;
+			ret = new;
 		}
+	}
+	return ret;
+}
 
-		if (is_empty_line(line, linelen)) {
-			if (!body)
-				continue;
-			if (fmt == CMIT_FMT_SHORT)
-				break;
-		} else {
-			body = 1;
+struct commit_list *get_merge_bases_many(struct commit *one,
+					 int n,
+					 struct commit **twos,
+					 int cleanup)
+{
+	struct commit_list *list;
+	struct commit **rslt;
+	struct commit_list *result;
+	int cnt, i, j;
+
+	result = merge_bases_many(one, n, twos);
+	for (i = 0; i < n; i++) {
+		if (one == twos[i])
+			return result;
+	}
+	if (!result || !result->next) {
+		if (cleanup) {
+			clear_commit_marks(one, all_flags);
+			for (i = 0; i < n; i++)
+				clear_commit_marks(twos[i], all_flags);
 		}
+		return result;
+	}
 
-		memset(buf + offset, ' ', indent);
-		memcpy(buf + offset + indent, line, linelen);
-		offset += linelen + indent;
-		if (fmt == CMIT_FMT_ONELINE)
-			break;
+	/* There are more than one */
+	cnt = 0;
+	list = result;
+	while (list) {
+		list = list->next;
+		cnt++;
 	}
-	if (fmt == CMIT_FMT_ONELINE) {
-		/* We do not want the terminating newline */
-		if (buf[offset - 1] == '\n')
-			offset--;
+	rslt = xcalloc(cnt, sizeof(*rslt));
+	for (list = result, i = 0; list; list = list->next)
+		rslt[i++] = list->item;
+	free_commit_list(result);
+
+	clear_commit_marks(one, all_flags);
+	for (i = 0; i < n; i++)
+		clear_commit_marks(twos[i], all_flags);
+	for (i = 0; i < cnt - 1; i++) {
+		for (j = i+1; j < cnt; j++) {
+			if (!rslt[i] || !rslt[j])
+				continue;
+			result = merge_bases_many(rslt[i], 1, &rslt[j]);
+			clear_commit_marks(rslt[i], all_flags);
+			clear_commit_marks(rslt[j], all_flags);
+			for (list = result; list; list = list->next) {
+				if (rslt[i] == list->item)
+					rslt[i] = NULL;
+				if (rslt[j] == list->item)
+					rslt[j] = NULL;
+			}
+		}
 	}
-	else {
-		/* Make sure there is an EOLN */
-		if (buf[offset - 1] != '\n')
-			buf[offset++] = '\n';
+
+	/* Surviving ones in rslt[] are the independent results */
+	result = NULL;
+	for (i = 0; i < cnt; i++) {
+		if (rslt[i])
+			commit_list_insert_by_date(rslt[i], &result);
 	}
-	buf[offset] = '\0';
-	return offset;
+	free(rslt);
+	return result;
 }
 
-struct commit *pop_commit(struct commit_list **stack)
+struct commit_list *get_merge_bases(struct commit *one, struct commit *two,
+				    int cleanup)
 {
-	struct commit_list *top = *stack;
-	struct commit *item = top ? top->item : NULL;
+	return get_merge_bases_many(one, 1, &two, cleanup);
+}
 
-	if (top) {
-		*stack = top->next;
-		free(top);
+int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
+{
+	if (!with_commit)
+		return 1;
+	while (with_commit) {
+		struct commit *other;
+
+		other = with_commit->item;
+		with_commit = with_commit->next;
+		if (in_merge_bases(other, &commit, 1))
+			return 1;
 	}
-	return item;
+	return 0;
 }
 
-int count_parents(struct commit * commit)
+int in_merge_bases(struct commit *commit, struct commit **reference, int num)
 {
-        int count = 0;
-        struct commit_list * parents = commit->parents;
-        for (count=0;parents; parents=parents->next,count++)
-          ;
-        return count;
+	struct commit_list *bases, *b;
+	int ret = 0;
+
+	if (num == 1)
+		bases = get_merge_bases(commit, *reference, 1);
+	else
+		die("not yet");
+	for (b = bases; b; b = b->next) {
+		if (!hashcmp(commit->object.sha1, b->item->object.sha1)) {
+			ret = 1;
+			break;
+		}
+	}
+
+	free_commit_list(bases);
+	return ret;
 }
 
-/*
- * Performs an in-place topological sort on the list supplied.
- */
-void sort_in_topological_order(struct commit_list ** list, int lifo)
+struct commit_list *reduce_heads(struct commit_list *heads)
 {
-	struct commit_list * next = *list;
-	struct commit_list * work = NULL, **insert;
-	struct commit_list ** pptr = list;
-	struct sort_node * nodes;
-	struct sort_node * next_nodes;
-	int count = 0;
+	struct commit_list *p;
+	struct commit_list *result = NULL, **tail = &result;
+	struct commit **other;
+	size_t num_head, num_other;
 
-	/* determine the size of the list */
-	while (next) {
-		next = next->next;
-		count++;
-	}
-	
-	if (!count)
-		return;
-	/* allocate an array to help sort the list */
-	nodes = xcalloc(count, sizeof(*nodes));
-	/* link the list to the array */
-	next_nodes = nodes;
-	next=*list;
-	while (next) {
-		next_nodes->list_item = next;
-		next->item->object.util = next_nodes;
-		next_nodes++;
-		next = next->next;
-	}
-	/* update the indegree */
-	next=*list;
-	while (next) {
-		struct commit_list * parents = next->item->parents;
-		while (parents) {
-			struct commit * parent=parents->item;
-			struct sort_node * pn = (struct sort_node *)parent->object.util;
-			
-			if (pn)
-				pn->indegree++;
-			parents=parents->next;
-		}
-		next=next->next;
-	}
-	/* 
-         * find the tips
-         *
-         * tips are nodes not reachable from any other node in the list 
-         * 
-         * the tips serve as a starting set for the work queue.
-         */
-	next=*list;
-	insert = &work;
-	while (next) {
-		struct sort_node * node = (struct sort_node *)next->item->object.util;
+	if (!heads)
+		return NULL;
 
-		if (node->indegree == 0) {
-			insert = &commit_list_insert(next->item, insert)->next;
-		}
-		next=next->next;
-	}
+	/* Avoid unnecessary reallocations */
+	for (p = heads, num_head = 0; p; p = p->next)
+		num_head++;
+	other = xcalloc(sizeof(*other), num_head);
 
-	/* process the list in topological order */
-	if (!lifo)
-		sort_by_date(&work);
-	while (work) {
-		struct commit * work_item = pop_commit(&work);
-		struct sort_node * work_node = (struct sort_node *)work_item->object.util;
-		struct commit_list * parents = work_item->parents;
+	/* For each commit, see if it can be reached by others */
+	for (p = heads; p; p = p->next) {
+		struct commit_list *q, *base;
 
-		while (parents) {
-			struct commit * parent=parents->item;
-			struct sort_node * pn = (struct sort_node *)parent->object.util;
-			
-			if (pn) {
-				/* 
-				 * parents are only enqueued for emission 
-                                 * when all their children have been emitted thereby
-                                 * guaranteeing topological order.
-                                 */
-				pn->indegree--;
-				if (!pn->indegree) {
-					if (!lifo)
-						insert_by_date(parent, &work);
-					else
-						commit_list_insert(parent, &work);
-				}
-			}
-			parents=parents->next;
+		/* Do we already have this in the result? */
+		for (q = result; q; q = q->next)
+			if (p->item == q->item)
+				break;
+		if (q)
+			continue;
+
+		num_other = 0;
+		for (q = heads; q; q = q->next) {
+			if (p->item == q->item)
+				continue;
+			other[num_other++] = q->item;
 		}
+		if (num_other)
+			base = get_merge_bases_many(p->item, num_other, other, 1);
+		else
+			base = NULL;
 		/*
-                 * work_item is a commit all of whose children
-                 * have already been emitted. we can emit it now.
-                 */
-		*pptr = work_node->list_item;
-		pptr = &(*pptr)->next;
-		*pptr = NULL;
-		work_item->object.util = NULL;
-	}
-	free(nodes);
+		 * If p->item does not have anything common with other
+		 * commits, there won't be any merge base.  If it is
+		 * reachable from some of the others, p->item will be
+		 * the merge base.  If its history is connected with
+		 * others, but p->item is not reachable by others, we
+		 * will get something other than p->item back.
+		 */
+		if (!base || (base->item != p->item))
+			tail = &(commit_list_insert(p->item, tail)->next);
+		free_commit_list(base);
+	}
+	free(other);
+	return result;
+}
+
+static const char commit_utf8_warn[] =
+"Warning: commit message does not conform to UTF-8.\n"
+"You may want to amend it after fixing the message, or set the config\n"
+"variable i18n.commitencoding to the encoding your project uses.\n";
+
+int commit_tree(const char *msg, unsigned char *tree,
+		struct commit_list *parents, unsigned char *ret,
+		const char *author)
+{
+	int result;
+	int encoding_is_utf8;
+	struct strbuf buffer;
+
+	assert_sha1_type(tree, OBJ_TREE);
+
+	/* Not having i18n.commitencoding is the same as having utf-8 */
+	encoding_is_utf8 = is_encoding_utf8(git_commit_encoding);
+
+	strbuf_init(&buffer, 8192); /* should avoid reallocs for the headers */
+	strbuf_addf(&buffer, "tree %s\n", sha1_to_hex(tree));
+
+	/*
+	 * NOTE! This ordering means that the same exact tree merged with a
+	 * different order of parents will be a _different_ changeset even
+	 * if everything else stays the same.
+	 */
+	while (parents) {
+		struct commit_list *next = parents->next;
+		strbuf_addf(&buffer, "parent %s\n",
+			sha1_to_hex(parents->item->object.sha1));
+		free(parents);
+		parents = next;
+	}
+
+	/* Person/date information */
+	if (!author)
+		author = git_author_info(IDENT_ERROR_ON_NO_NAME);
+	strbuf_addf(&buffer, "author %s\n", author);
+	strbuf_addf(&buffer, "committer %s\n", git_committer_info(IDENT_ERROR_ON_NO_NAME));
+	if (!encoding_is_utf8)
+		strbuf_addf(&buffer, "encoding %s\n", git_commit_encoding);
+	strbuf_addch(&buffer, '\n');
+
+	/* And add the comment */
+	strbuf_addstr(&buffer, msg);
+
+	/* And check the encoding */
+	if (encoding_is_utf8 && !is_utf8(buffer.buf))
+		fprintf(stderr, commit_utf8_warn);
+
+	result = write_sha1_file(buffer.buf, buffer.len, commit_type, ret);
+	strbuf_release(&buffer);
+	return result;
 }