1 files changed, 102 insertions, 43 deletions

diff --git a/builtin/describe.c b/builtin/describe.c
index d7dd8139de..ffaf8d9f0a 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -23,6 +23,8 @@
 #include "list-objects.h"
 #include "commit-slab.h"
 #include "wildmatch.h"
+#include "prio-queue.h"
+#include "oidset.h"
 
 #define MAX_TAGS	(FLAG_BITS - 1)
 #define DEFAULT_CANDIDATES 10
@@ -249,36 +251,83 @@ static int compare_pt(const void *a_, const void *b_)
 	return 0;
 }
 
-static unsigned long finish_depth_computation(
-	struct commit_list **list,
-	struct possible_tag *best)
+struct lazy_queue {
+	struct prio_queue queue;
+	bool get_pending;
+};
+
+#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false }
+
+static void *lazy_queue_get(struct lazy_queue *queue)
+{
+	if (queue->get_pending)
+		prio_queue_get(&queue->queue);
+	else
+		queue->get_pending = true;
+	return prio_queue_peek(&queue->queue);
+}
+
+static void lazy_queue_put(struct lazy_queue *queue, void *thing)
+{
+	if (queue->get_pending)
+		prio_queue_replace(&queue->queue, thing);
+	else
+		prio_queue_put(&queue->queue, thing);
+	queue->get_pending = false;
+}
+
+static bool lazy_queue_empty(const struct lazy_queue *queue)
+{
+	return queue->queue.nr == (queue->get_pending ? 1 : 0);
+}
+
+static void lazy_queue_clear(struct lazy_queue *queue)
+{
+	clear_prio_queue(&queue->queue);
+	queue->get_pending = false;
+}
+
+static unsigned long finish_depth_computation(struct lazy_queue *queue,
+					      struct possible_tag *best)
 {
 	unsigned long seen_commits = 0;
-	while (*list) {
-		struct commit *c = pop_commit(list);
+	struct oidset unflagged = OIDSET_INIT;
+
+	for (size_t i = queue->get_pending ? 1 : 0; i < queue->queue.nr; i++) {
+		struct commit *commit = queue->queue.array[i].data;
+		if (!(commit->object.flags & best->flag_within))
+			oidset_insert(&unflagged, &commit->object.oid);
+	}
+
+	while (!lazy_queue_empty(queue)) {
+		struct commit *c = lazy_queue_get(queue);
 		struct commit_list *parents = c->parents;
 		seen_commits++;
 		if (c->object.flags & best->flag_within) {
-			struct commit_list *a = *list;
-			while (a) {
-				struct commit *i = a->item;
-				if (!(i->object.flags & best->flag_within))
-					break;
-				a = a->next;
-			}
-			if (!a)
+			if (!oidset_size(&unflagged))
 				break;
-		} else
+		} else {
+			oidset_remove(&unflagged, &c->object.oid);
 			best->depth++;
+		}
 		while (parents) {
+			unsigned seen, flag_before, flag_after;
 			struct commit *p = parents->item;
 			repo_parse_commit(the_repository, p);
-			if (!(p->object.flags & SEEN))
-				commit_list_insert_by_date(p, list);
+			seen = p->object.flags & SEEN;
+			if (!seen)
+				lazy_queue_put(queue, p);
+			flag_before = p->object.flags & best->flag_within;
 			p->object.flags |= c->object.flags;
+			flag_after = p->object.flags & best->flag_within;
+			if (!seen && !flag_after)
+				oidset_insert(&unflagged, &p->object.oid);
+			if (seen && !flag_before && flag_after)
+				oidset_remove(&unflagged, &p->object.oid);
 			parents = parents->next;
 		}
 	}
+	oidset_clear(&unflagged);
 	return seen_commits;
 }
 
@@ -313,18 +362,16 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf
 		    repo_find_unique_abbrev(the_repository, oid, abbrev));
 }
 
-static void describe_commit(struct object_id *oid, struct strbuf *dst)
+static void describe_commit(struct commit *cmit, struct strbuf *dst)
 {
-	struct commit *cmit, *gave_up_on = NULL;
-	struct commit_list *list;
+	struct commit *gave_up_on = NULL;
+	struct lazy_queue queue = LAZY_QUEUE_INIT;
 	struct commit_name *n;
 	struct possible_tag all_matches[MAX_TAGS];
 	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
 	unsigned long seen_commits = 0;
 	unsigned int unannotated_cnt = 0;
 
-	cmit = lookup_commit_reference(the_repository, oid);
-
 	n = find_commit_name(&cmit->object.oid);
 	if (n && (tags || all || n->prio == 2)) {
 		/*
@@ -332,7 +379,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 		 */
 		append_name(n, dst);
 		if (n->misnamed || longformat)
-			append_suffix(0, n->tag ? get_tagged_oid(n->tag) : oid, dst);
+			append_suffix(0, n->tag ? get_tagged_oid(n->tag) : &cmit->object.oid, dst);
 		if (suffix)
 			strbuf_addstr(dst, suffix);
 		return;
@@ -359,11 +406,10 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 		have_util = 1;
 	}
 
-	list = NULL;
 	cmit->object.flags = SEEN;
-	commit_list_insert(cmit, &list);
-	while (list) {
-		struct commit *c = pop_commit(&list);
+	lazy_queue_put(&queue, cmit);
+	while (!lazy_queue_empty(&queue)) {
+		struct commit *c = lazy_queue_get(&queue);
 		struct commit_list *parents = c->parents;
 		struct commit_name **slot;
 
@@ -397,7 +443,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 				t->depth++;
 		}
 		/* Stop if last remaining path already covered by best candidate(s) */
-		if (annotated_cnt && !list) {
+		if (annotated_cnt && lazy_queue_empty(&queue)) {
 			int best_depth = INT_MAX;
 			unsigned best_within = 0;
 			for (cur_match = 0; cur_match < match_cnt; cur_match++) {
@@ -420,7 +466,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 			struct commit *p = parents->item;
 			repo_parse_commit(the_repository, p);
 			if (!(p->object.flags & SEEN))
-				commit_list_insert_by_date(p, &list);
+				lazy_queue_put(&queue, p);
 			p->object.flags |= c->object.flags;
 			parents = parents->next;
 
@@ -435,6 +481,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 			strbuf_add_unique_abbrev(dst, cmit_oid, abbrev);
 			if (suffix)
 				strbuf_addstr(dst, suffix);
+			lazy_queue_clear(&queue);
 			return;
 		}
 		if (unannotated_cnt)
@@ -450,11 +497,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 	QSORT(all_matches, match_cnt, compare_pt);
 
 	if (gave_up_on) {
-		commit_list_insert_by_date(gave_up_on, &list);
+		lazy_queue_put(&queue, gave_up_on);
 		seen_commits--;
 	}
-	seen_commits += finish_depth_computation(&list, &all_matches[0]);
-	free_commit_list(list);
+	seen_commits += finish_depth_computation(&queue, &all_matches[0]);
+	lazy_queue_clear(&queue);
 
 	if (debug) {
 		static int label_width = -1;
@@ -489,8 +536,8 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 }
 
 struct process_commit_data {
-	struct object_id current_commit;
-	struct object_id looking_for;
+	struct commit *current_commit;
+	const struct object_id *looking_for;
 	struct strbuf *dst;
 	struct rev_info *revs;
 };
@@ -498,34 +545,43 @@ struct process_commit_data {
 static void process_commit(struct commit *commit, void *data)
 {
 	struct process_commit_data *pcd = data;
-	pcd->current_commit = commit->object.oid;
+	pcd->current_commit = commit;
 }
 
 static void process_object(struct object *obj, const char *path, void *data)
 {
 	struct process_commit_data *pcd = data;
 
-	if (oideq(&pcd->looking_for, &obj->oid) && !pcd->dst->len) {
+	if (oideq(pcd->looking_for, &obj->oid) && !pcd->dst->len) {
 		reset_revision_walk();
-		describe_commit(&pcd->current_commit, pcd->dst);
-		strbuf_addf(pcd->dst, ":%s", path);
+		if (pcd->current_commit) {
+			describe_commit(pcd->current_commit, pcd->dst);
+			strbuf_addf(pcd->dst, ":%s", path);
+		}
 		free_commit_list(pcd->revs->commits);
 		pcd->revs->commits = NULL;
 	}
 }
 
-static void describe_blob(struct object_id oid, struct strbuf *dst)
+static void describe_blob(const struct object_id *oid, struct strbuf *dst)
 {
 	struct rev_info revs;
 	struct strvec args = STRVEC_INIT;
-	struct process_commit_data pcd = { *null_oid(the_hash_algo), oid, dst, &revs};
+	struct object_id head_oid;
+	struct process_commit_data pcd = { NULL, oid, dst, &revs};
+
+	if (repo_get_oid(the_repository, "HEAD", &head_oid))
+		die(_("cannot search for blob '%s' on an unborn branch"),
+		    oid_to_hex(oid));
 
 	strvec_pushl(&args, "internal: The first arg is not parsed",
-		     "--objects", "--in-commit-order", "--reverse", "HEAD",
+		     "--objects", "--in-commit-order", "--reverse",
+		     oid_to_hex(&head_oid),
 		     NULL);
 
 	repo_init_revisions(the_repository, &revs, NULL);
-	if (setup_revisions(args.nr, args.v, &revs, NULL) > 1)
+	setup_revisions_from_strvec(&args, &revs, NULL);
+	if (args.nr > 1)
 		BUG("setup_revisions could not handle all args?");
 
 	if (prepare_revision_walk(&revs))
@@ -535,6 +591,9 @@ static void describe_blob(struct object_id oid, struct strbuf *dst)
 	reset_revision_walk();
 	release_revisions(&revs);
 	strvec_clear(&args);
+
+	if (!dst->len)
+		die(_("blob '%s' not reachable from HEAD"), oid_to_hex(oid));
 }
 
 static void describe(const char *arg, int last_one)
@@ -551,10 +610,10 @@ static void describe(const char *arg, int last_one)
 	cmit = lookup_commit_reference_gently(the_repository, &oid, 1);
 
 	if (cmit)
-		describe_commit(&oid, &sb);
+		describe_commit(cmit, &sb);
 	else if (odb_read_object_info(the_repository->objects,
 				      &oid, NULL) == OBJ_BLOB)
-		describe_blob(oid, &sb);
+		describe_blob(&oid, &sb);
 	else
 		die(_("%s is neither a commit nor blob"), arg);