X-Git-Url: https://git.tokkee.org/?a=blobdiff_plain;ds=sidebyside;f=commit.c;h=dc0c5bfdab7296bf7febb6f1b1aad64550838c15;hb=d592b3157f70c9dac6288b28c46a64826c0abd18;hp=f074811edc8c5ba41351f50c48a6cda7614e8f8e;hpb=8256c6e0107a51b2714f2e068b693025e4ddcae8;p=git.git

diff --git a/commit.c b/commit.c
index f074811ed..dc0c5bfda 100644
--- a/commit.c
+++ b/commit.c
@@ -48,19 +48,32 @@ struct commit *lookup_commit(const unsigned char *sha1)
 	return check_commit(obj, sha1, 0);
 }
 
-static unsigned long parse_commit_date(const char *buf)
+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 (buf >= tail)
+		return 0;
+	/* dateptr < buf && buf[-1] == '\n', so strtoul will stop at buf-1 */
+	date = strtoul(dateptr, NULL, 10);
 	if (date == ULONG_MAX)
 		date = 0;
 	return date;
@@ -180,7 +193,7 @@ static void prepare_commit_graft(void)
 	commit_graft_prepared = 1;
 }
 
-static struct commit_graft *lookup_commit_graft(const unsigned char *sha1)
+struct commit_graft *lookup_commit_graft(const unsigned char *sha1)
 {
 	int pos;
 	prepare_commit_graft();
@@ -230,20 +243,17 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)
 	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;
 	tail += size;
-	if (tail <= bufptr + 5 || memcmp(bufptr, "tree ", 5))
+	if (tail <= bufptr + 46 || memcmp(bufptr, "tree ", 5) || bufptr[45] != '\n')
 		return error("bogus commit object %s", sha1_to_hex(item->object.sha1));
-	if (tail <= bufptr + 45 || get_sha1_hex(bufptr + 5, parent) < 0)
+	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;
 
@@ -259,10 +269,8 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)
 		if (graft)
 			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;
@@ -272,21 +280,9 @@ 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;
 }
@@ -298,6 +294,8 @@ int parse_commit(struct commit *item)
 	unsigned long size;
 	int ret;
 
+	if (!item)
+		return -1;
 	if (item->object.parsed)
 		return 0;
 	buffer = read_sha1_file(item->object.sha1, &type, &size);
@@ -327,6 +325,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) {
@@ -372,8 +378,7 @@ 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);
 		}
@@ -431,8 +436,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	/* Mark them and clear the indegree */
 	for (next = orig; next; next = next->next) {
 		struct commit *commit = next->item;
-		commit->object.flags |= TOPOSORT;
-		commit->indegree = 0;
+		commit->indegree = 1;
 	}
 
 	/* update the indegree */
@@ -441,7 +445,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		while (parents) {
 			struct commit *parent = parents->item;
 
-			if (parent->object.flags & TOPOSORT)
+			if (parent->indegree)
 				parent->indegree++;
 			parents = parents->next;
 		}
@@ -459,7 +463,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	for (next = orig; next; next = next->next) {
 		struct commit *commit = next->item;
 
-		if (!commit->indegree)
+		if (commit->indegree == 1)
 			insert = &commit_list_insert(commit, insert)->next;
 	}
 
@@ -481,7 +485,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		for (parents = commit->parents; parents ; parents = parents->next) {
 			struct commit *parent=parents->item;
 
-			if (!(parent->object.flags & TOPOSORT))
+			if (!parent->indegree)
 				continue;
 
 			/*
@@ -489,7 +493,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 			 * when all their children have been emitted thereby
 			 * guaranteeing topological order.
 			 */
-			if (!--parent->indegree) {
+			if (--parent->indegree == 1) {
 				if (!lifo)
 					insert_by_date(parent, &work);
 				else
@@ -500,7 +504,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		 * work_item is a commit all of whose children
 		 * have already been emitted. we can emit it now.
 		 */
-		commit->object.flags &= ~TOPOSORT;
+		commit->indegree = 0;
 		*pptr = work_item;
 		pptr = &work_item->next;
 	}
@@ -528,24 +532,34 @@ static struct commit *interesting(struct commit_list *list)
 	return NULL;
 }
 
-static struct commit_list *merge_bases(struct commit *one, struct commit *two)
+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 (one == two)
-		/* We do not mark this even with RESULT so we do not
-		 * have to clean it up.
-		 */
-		return commit_list_insert(one, &result);
+	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);
+	}
 
-	parse_commit(one);
-	parse_commit(two);
+	if (parse_commit(one))
+		return NULL;
+	for (i = 0; i < n; i++) {
+		if (parse_commit(twos[i]))
+			return NULL;
+	}
 
 	one->object.flags |= PARENT1;
-	two->object.flags |= PARENT2;
 	insert_by_date(one, &list);
-	insert_by_date(two, &list);
+	for (i = 0; i < n; i++) {
+		twos[i]->object.flags |= PARENT2;
+		insert_by_date(twos[i], &list);
+	}
 
 	while (interesting(list)) {
 		struct commit *commit;
@@ -573,7 +587,8 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)
 			parents = parents->next;
 			if ((p->object.flags & flags) == flags)
 				continue;
-			parse_commit(p);
+			if (parse_commit(p))
+				return NULL;
 			p->object.flags |= flags;
 			insert_by_date(p, &list);
 		}
@@ -592,21 +607,53 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)
 	return result;
 }
 
-struct commit_list *get_merge_bases(struct commit *one,
-					struct commit *two, int cleanup)
+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;
+			}
+			ret = new;
+		}
+	}
+	return ret;
+}
+
+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(one, two);
-	if (one == two)
-		return result;
+	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);
-			clear_commit_marks(two, all_flags);
+			for (i = 0; i < n; i++)
+				clear_commit_marks(twos[i], all_flags);
 		}
 		return result;
 	}
@@ -624,12 +671,13 @@ struct commit_list *get_merge_bases(struct commit *one,
 	free_commit_list(result);
 
 	clear_commit_marks(one, all_flags);
-	clear_commit_marks(two, 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(rslt[i], rslt[j]);
+			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) {
@@ -651,6 +699,12 @@ struct commit_list *get_merge_bases(struct commit *one,
 	return result;
 }
 
+struct commit_list *get_merge_bases(struct commit *one, struct commit *two,
+				    int cleanup)
+{
+	return get_merge_bases_many(one, 1, &two, cleanup);
+}
+
 int in_merge_bases(struct commit *commit, struct commit **reference, int num)
 {
 	struct commit_list *bases, *b;
@@ -670,3 +724,55 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)
 	free_commit_list(bases);
 	return ret;
 }
+
+struct commit_list *reduce_heads(struct commit_list *heads)
+{
+	struct commit_list *p;
+	struct commit_list *result = NULL, **tail = &result;
+	struct commit **other;
+	size_t num_head, num_other;
+
+	if (!heads)
+		return NULL;
+
+	/* Avoid unnecessary reallocations */
+	for (p = heads, num_head = 0; p; p = p->next)
+		num_head++;
+	other = xcalloc(sizeof(*other), num_head);
+
+	/* For each commit, see if it can be reached by others */
+	for (p = heads; p; p = p->next) {
+		struct commit_list *q, *base;
+
+		/* 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;
+		/*
+		 * 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;
+}