X-Git-Url: https://git.tokkee.org/?a=blobdiff_plain;f=builtin-describe.c;h=669110cb0645629ca5b152d8328aa91d63be1550;hb=0cae23467ada9b94210a0e770064841efea8ad40;hp=5d6865b165043096f6151138bc1c6e5ffc5be3a8;hpb=910c0d7b5ea09d55f769062abd9b9fe3af904a23;p=git.git

diff --git a/builtin-describe.c b/builtin-describe.c
index 5d6865b16..669110cb0 100644
--- a/builtin-describe.c
+++ b/builtin-describe.c
@@ -2,69 +2,42 @@
 #include "commit.h"
 #include "tag.h"
 #include "refs.h"
-#include "diff.h"
-#include "diffcore.h"
-#include "revision.h"
 #include "builtin.h"
+#include "exec_cmd.h"
+
+#define SEEN		(1u<<0)
+#define MAX_TAGS	(FLAG_BITS - 1)
 
 static const char describe_usage[] =
 "git-describe [--all] [--tags] [--abbrev=<n>] <committish>*";
 
+static int debug;	/* Display lots of verbose info */
 static int all;	/* Default to annotated tags only */
 static int tags;	/* But allow any tags if --tags is specified */
 static int abbrev = DEFAULT_ABBREV;
+static int max_candidates = 10;
 
-static unsigned int names[256], allocs[256];
-static struct commit_name {
-	struct commit *commit;
+struct commit_name {
 	int prio; /* annotated tag = 2, tag = 1, head = 0 */
 	char path[FLEX_ARRAY]; /* more */
-} **name_array[256];
-
-static struct commit_name *match(struct commit *cmit)
-{
-	unsigned char level0 = cmit->object.sha1[0];
-	struct commit_name **p = name_array[level0];
-	unsigned int hi = names[level0];
-	unsigned int lo = 0;
-
-	while (lo < hi) {
-		unsigned int mi = (lo + hi) / 2;
-		int cmp = hashcmp(p[mi]->commit->object.sha1,
-			cmit->object.sha1);
-		if (!cmp) {
-			while (mi && p[mi - 1]->commit == cmit)
-				mi--;
-			return p[mi];
-		}
-		if (cmp > 0)
-			hi = mi;
-		else
-			lo = mi+1;
-	}
-	return NULL;
-}
+};
+static const char *prio_names[] = {
+	"head", "lightweight", "annotated",
+};
 
 static void add_to_known_names(const char *path,
 			       struct commit *commit,
 			       int prio)
 {
-	int idx;
-	int len = strlen(path)+1;
-	struct commit_name *name = xmalloc(sizeof(struct commit_name) + len);
-	unsigned char m = commit->object.sha1[0];
-
-	name->commit = commit;
-	name->prio = prio;
-	memcpy(name->path, path, len);
-	idx = names[m];
-	if (idx >= allocs[m]) {
-		allocs[m] = (idx + 50) * 3 / 2;
-		name_array[m] = xrealloc(name_array[m],
-			allocs[m] * sizeof(*name_array));
+	struct commit_name *e = commit->util;
+	if (!e || e->prio < prio) {
+		size_t len = strlen(path)+1;
+		free(e);
+		e = xmalloc(sizeof(struct commit_name) + len);
+		e->prio = prio;
+		memcpy(e->path, path, len);
+		commit->util = e;
 	}
-	name_array[m][idx] = name;
-	names[m] = ++idx;
 }
 
 static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)
@@ -80,7 +53,7 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void
 	 * If --tags, then any tags are used.
 	 * Otherwise only annotated tags are used.
 	 */
-	if (!strncmp(path, "refs/tags/", 10)) {
+	if (!prefixcmp(path, "refs/tags/")) {
 		if (object->type == OBJ_TAG)
 			prio = 2;
 		else
@@ -99,35 +72,69 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void
 	return 0;
 }
 
-static int compare_names(const void *_a, const void *_b)
-{
-	struct commit_name *a = *(struct commit_name **)_a;
-	struct commit_name *b = *(struct commit_name **)_b;
-	unsigned long a_date = a->commit->date;
-	unsigned long b_date = b->commit->date;
-	int cmp = hashcmp(a->commit->object.sha1, b->commit->object.sha1);
-
-	if (cmp)
-		return cmp;
-	if (a->prio != b->prio)
-		return b->prio - a->prio;
-	return (a_date > b_date) ? -1 : (a_date == b_date) ? 0 : 1;
-}
-
 struct possible_tag {
-	struct possible_tag *next;
 	struct commit_name *name;
-	unsigned long depth;
+	int depth;
+	int found_order;
+	unsigned flag_within;
 };
 
+static int compare_pt(const void *a_, const void *b_)
+{
+	struct possible_tag *a = (struct possible_tag *)a_;
+	struct possible_tag *b = (struct possible_tag *)b_;
+	if (a->name->prio != b->name->prio)
+		return b->name->prio - a->name->prio;
+	if (a->depth != b->depth)
+		return a->depth - b->depth;
+	if (a->found_order != b->found_order)
+		return a->found_order - b->found_order;
+	return 0;
+}
+
+static unsigned long finish_depth_computation(
+	struct commit_list **list,
+	struct possible_tag *best)
+{
+	unsigned long seen_commits = 0;
+	while (*list) {
+		struct commit *c = pop_commit(list);
+		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)
+				break;
+		} else
+			best->depth++;
+		while (parents) {
+			struct commit *p = parents->item;
+			parse_commit(p);
+			if (!(p->object.flags & SEEN))
+				insert_by_date(p, list);
+			p->object.flags |= c->object.flags;
+			parents = parents->next;
+		}
+	}
+	return seen_commits;
+}
+
 static void describe(const char *arg, int last_one)
 {
 	unsigned char sha1[20];
-	struct commit *cmit;
+	struct commit *cmit, *gave_up_on = NULL;
 	struct commit_list *list;
 	static int initialized = 0;
 	struct commit_name *n;
-	struct possible_tag *all_matches, *min_match, *cur_match;
+	struct possible_tag all_matches[MAX_TAGS];
+	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
+	unsigned long seen_commits = 0;
 
 	if (get_sha1(arg, sha1))
 		die("Not a valid object name %s", arg);
@@ -136,111 +143,149 @@ static void describe(const char *arg, int last_one)
 		die("%s is not a valid '%s' object", arg, commit_type);
 
 	if (!initialized) {
-		unsigned int m;
 		initialized = 1;
 		for_each_ref(get_name, NULL);
-		for (m = 0; m < ARRAY_SIZE(name_array); m++)
-			qsort(name_array[m], names[m],
-				sizeof(*name_array[m]), compare_names);
 	}
 
-	n = match(cmit);
+	n = cmit->util;
 	if (n) {
 		printf("%s\n", n->path);
 		return;
 	}
 
+	if (debug)
+		fprintf(stderr, "searching to describe %s\n", arg);
+
 	list = NULL;
-	all_matches = NULL;
-	cur_match = NULL;
+	cmit->object.flags = SEEN;
 	commit_list_insert(cmit, &list);
 	while (list) {
 		struct commit *c = pop_commit(&list);
 		struct commit_list *parents = c->parents;
-		n = match(c);
+		seen_commits++;
+		n = c->util;
 		if (n) {
-			struct possible_tag *p = xmalloc(sizeof(*p));
-			p->name = n;
-			p->next = NULL;
-			if (cur_match)
-				cur_match->next = p;
-			else
-				all_matches = p;
-			cur_match = p;
-			if (n->prio == 2)
-				continue;
+			if (match_cnt < max_candidates) {
+				struct possible_tag *t = &all_matches[match_cnt++];
+				t->name = n;
+				t->depth = seen_commits - 1;
+				t->flag_within = 1u << match_cnt;
+				t->found_order = match_cnt;
+				c->object.flags |= t->flag_within;
+				if (n->prio == 2)
+					annotated_cnt++;
+			}
+			else {
+				gave_up_on = c;
+				break;
+			}
+		}
+		for (cur_match = 0; cur_match < match_cnt; cur_match++) {
+			struct possible_tag *t = &all_matches[cur_match];
+			if (!(c->object.flags & t->flag_within))
+				t->depth++;
+		}
+		if (annotated_cnt && !list) {
+			if (debug)
+				fprintf(stderr, "finished search at %s\n",
+					sha1_to_hex(c->object.sha1));
+			break;
 		}
 		while (parents) {
 			struct commit *p = parents->item;
 			parse_commit(p);
-			if (!(p->object.flags & SEEN)) {
-				p->object.flags |= SEEN;
+			if (!(p->object.flags & SEEN))
 				insert_by_date(p, &list);
-			}
+			p->object.flags |= c->object.flags;
 			parents = parents->next;
 		}
 	}
 
-	if (!all_matches)
+	if (!match_cnt)
 		die("cannot describe '%s'", sha1_to_hex(cmit->object.sha1));
 
-	min_match = NULL;
-	for (cur_match = all_matches; cur_match; cur_match = cur_match->next) {
-		struct rev_info revs;
-		struct commit *tagged = cur_match->name->commit;
+	qsort(all_matches, match_cnt, sizeof(all_matches[0]), compare_pt);
 
-		clear_commit_marks(cmit, -1);
-		init_revisions(&revs, NULL);
-		tagged->object.flags |= UNINTERESTING;
-		add_pending_object(&revs, &tagged->object, NULL);
-		add_pending_object(&revs, &cmit->object, NULL);
-
-		prepare_revision_walk(&revs);
-		cur_match->depth = 0;
-		while ((!min_match || cur_match->depth < min_match->depth)
-			&& get_revision(&revs))
-			cur_match->depth++;
-		if (!min_match || (cur_match->depth < min_match->depth
-			&& cur_match->name->prio >= min_match->name->prio))
-			min_match = cur_match;
-		free_commit_list(revs.commits);
+	if (gave_up_on) {
+		insert_by_date(gave_up_on, &list);
+		seen_commits--;
 	}
-	printf("%s-g%s\n", min_match->name->path,
-		   find_unique_abbrev(cmit->object.sha1, abbrev));
+	seen_commits += finish_depth_computation(&list, &all_matches[0]);
+	free_commit_list(list);
 
-	if (!last_one) {
-		for (cur_match = all_matches; cur_match; cur_match = min_match) {
-			min_match = cur_match->next;
-			free(cur_match);
+	if (debug) {
+		for (cur_match = 0; cur_match < match_cnt; cur_match++) {
+			struct possible_tag *t = &all_matches[cur_match];
+			fprintf(stderr, " %-11s %8d %s\n",
+				prio_names[t->name->prio],
+				t->depth, t->name->path);
+		}
+		fprintf(stderr, "traversed %lu commits\n", seen_commits);
+		if (gave_up_on) {
+			fprintf(stderr,
+				"more than %i tags found; listed %i most recent\n"
+				"gave up search at %s\n",
+				max_candidates, max_candidates,
+				sha1_to_hex(gave_up_on->object.sha1));
 		}
-		clear_commit_marks(cmit, SEEN);
 	}
+	if (abbrev == 0)
+		printf("%s\n", all_matches[0].name->path );
+	else
+		printf("%s-%d-g%s\n", all_matches[0].name->path,
+		       all_matches[0].depth,
+		       find_unique_abbrev(cmit->object.sha1, abbrev));
+
+	if (!last_one)
+		clear_commit_marks(cmit, -1);
 }
 
 int cmd_describe(int argc, const char **argv, const char *prefix)
 {
 	int i;
+	int contains = 0;
 
 	for (i = 1; i < argc; i++) {
 		const char *arg = argv[i];
 
 		if (*arg != '-')
 			break;
+		else if (!strcmp(arg, "--contains"))
+			contains = 1;
+		else if (!strcmp(arg, "--debug"))
+			debug = 1;
 		else if (!strcmp(arg, "--all"))
 			all = 1;
 		else if (!strcmp(arg, "--tags"))
 			tags = 1;
-		else if (!strncmp(arg, "--abbrev=", 9)) {
+		else if (!prefixcmp(arg, "--abbrev=")) {
 			abbrev = strtoul(arg + 9, NULL, 10);
-			if (abbrev < MINIMUM_ABBREV || 40 < abbrev)
+			if (abbrev != 0 && (abbrev < MINIMUM_ABBREV || 40 < abbrev))
 				abbrev = DEFAULT_ABBREV;
 		}
+		else if (!prefixcmp(arg, "--candidates=")) {
+			max_candidates = strtoul(arg + 13, NULL, 10);
+			if (max_candidates < 1)
+				max_candidates = 1;
+			else if (max_candidates > MAX_TAGS)
+				max_candidates = MAX_TAGS;
+		}
 		else
 			usage(describe_usage);
 	}
 
 	save_commit_buffer = 0;
 
+	if (contains) {
+		const char **args = xmalloc((4 + argc - i) * sizeof(char*));
+		args[0] = "name-rev";
+		args[1] = "--name-only";
+		args[2] = "--tags";
+		memcpy(args + 3, argv + i, (argc - i) * sizeof(char*));
+		args[3 + argc - i] = NULL;
+		return cmd_name_rev(3 + argc - i, args, prefix);
+	}
+
 	if (argc <= i)
 		describe("HEAD", 1);
 	else