[PATCH 2/3] Make git-describe a builtin.

[PATCH 2/3] Make git-describe a builtin.

[Shawn O. Pearce]

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 Makefile           |    3 +-
 builtin-describe.c |  176 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 builtin.h          |    1 +
 describe.c         |  176 ----------------------------------------------------
 git.c              |    1 +
 5 files changed, 180 insertions(+), 177 deletions(-)

diff --git a/Makefile b/Makefile
index de746be..f648085 100644
--- a/Makefile
+++ b/Makefile
@@ -203,7 +203,7 @@ PROGRAMS = \
 	git-update-server-info$X \
 	git-upload-pack$X git-verify-pack$X \
 	git-pack-redundant$X git-var$X \
-	git-describe$X git-merge-tree$X git-imap-send$X \
+	git-merge-tree$X git-imap-send$X \
 	git-merge-recursive$X \
 	$(EXTRA_PROGRAMS)
 
@@ -274,6 +274,7 @@ BUILTIN_OBJS = \
 	builtin-check-ref-format.o \
 	builtin-commit-tree.o \
 	builtin-count-objects.o \
+	builtin-describe.o \
 	builtin-diff.o \
 	builtin-diff-files.o \
 	builtin-diff-index.o \
diff --git a/builtin-describe.c b/builtin-describe.c
new file mode 100644
index 0000000..ad3b469
--- /dev/null
+++ b/builtin-describe.c
@@ -0,0 +1,176 @@
+#include "cache.h"
+#include "commit.h"
+#include "tag.h"
+#include "refs.h"
+#include "builtin.h"
+
+#define SEEN (1u << 0)
+
+static const char describe_usage[] =
+"git-describe [--all] [--tags] [--abbrev=<n>] <committish>*";
+
+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 names, allocs;
+static struct commit_name {
+	const struct commit *commit;
+	int prio; /* annotated tag = 2, tag = 1, head = 0 */
+	char path[FLEX_ARRAY]; /* more */
+} **name_array = NULL;
+
+static struct commit_name *match(struct commit *cmit)
+{
+	int i = names;
+	struct commit_name **p = name_array;
+
+	while (i-- > 0) {
+		struct commit_name *n = *p++;
+		if (n->commit == cmit)
+			return n;
+	}
+	return NULL;
+}
+
+static void add_to_known_names(const char *path,
+			       const struct commit *commit,
+			       int prio)
+{
+	int idx;
+	int len = strlen(path)+1;
+	struct commit_name *name = xmalloc(sizeof(struct commit_name) + len);
+
+	name->commit = commit;
+	name->prio = prio;
+	memcpy(name->path, path, len);
+	idx = names;
+	if (idx >= allocs) {
+		allocs = (idx + 50) * 3 / 2;
+		name_array = xrealloc(name_array, allocs*sizeof(*name_array));
+	}
+	name_array[idx] = name;
+	names = ++idx;
+}
+
+static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)
+{
+	struct commit *commit = lookup_commit_reference_gently(sha1, 1);
+	struct object *object;
+	int prio;
+
+	if (!commit)
+		return 0;
+	object = parse_object(sha1);
+	/* If --all, then any refs are used.
+	 * If --tags, then any tags are used.
+	 * Otherwise only annotated tags are used.
+	 */
+	if (!strncmp(path, "refs/tags/", 10)) {
+		if (object->type == OBJ_TAG)
+			prio = 2;
+		else
+			prio = 1;
+	}
+	else
+		prio = 0;
+
+	if (!all) {
+		if (!prio)
+			return 0;
+		if (!tags && prio < 2)
+			return 0;
+	}
+	add_to_known_names(all ? path + 5 : path + 10, commit, prio);
+	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;
+
+	if (a->prio != b->prio)
+		return b->prio - a->prio;
+	return (a_date > b_date) ? -1 : (a_date == b_date) ? 0 : 1;
+}
+
+static void describe(const char *arg, int last_one)
+{
+	unsigned char sha1[20];
+	struct commit *cmit;
+	struct commit_list *list;
+	static int initialized = 0;
+	struct commit_name *n;
+
+	if (get_sha1(arg, sha1))
+		die("Not a valid object name %s", arg);
+	cmit = lookup_commit_reference(sha1);
+	if (!cmit)
+		die("%s is not a valid '%s' object", arg, commit_type);
+
+	if (!initialized) {
+		initialized = 1;
+		for_each_ref(get_name, NULL);
+		qsort(name_array, names, sizeof(*name_array), compare_names);
+	}
+
+	n = match(cmit);
+	if (n) {
+		printf("%s\n", n->path);
+		return;
+	}
+
+	list = NULL;
+	commit_list_insert(cmit, &list);
+	while (list) {
+		struct commit *c = pop_most_recent_commit(&list, SEEN);
+		n = match(c);
+		if (n) {
+			printf("%s-g%s\n", n->path,
+			       find_unique_abbrev(cmit->object.sha1, abbrev));
+			if (!last_one)
+				clear_commit_marks(cmit, SEEN);
+			return;
+		}
+	}
+	die("cannot describe '%s'", sha1_to_hex(cmit->object.sha1));
+}
+
+int cmd_describe(int argc, const char **argv, const char *prefix)
+{
+	int i;
+
+	for (i = 1; i < argc; i++) {
+		const char *arg = argv[i];
+
+		if (*arg != '-')
+			break;
+		else if (!strcmp(arg, "--all"))
+			all = 1;
+		else if (!strcmp(arg, "--tags"))
+			tags = 1;
+		else if (!strncmp(arg, "--abbrev=", 9)) {
+			abbrev = strtoul(arg + 9, NULL, 10);
+			if (abbrev < MINIMUM_ABBREV || 40 < abbrev)
+				abbrev = DEFAULT_ABBREV;
+		}
+		else
+			usage(describe_usage);
+	}
+
+	save_commit_buffer = 0;
+
+	if (argc <= i)
+		describe("HEAD", 1);
+	else
+		while (i < argc) {
+			describe(argv[i], (i == argc - 1));
+			i++;
+		}
+
+	return 0;
+}
diff --git a/builtin.h b/builtin.h
index ae32993..818c7bf 100644
--- a/builtin.h
+++ b/builtin.h
@@ -25,6 +25,7 @@ extern int cmd_check_ref_format(int argc, const char **argv, const char *prefix)
 extern int cmd_cherry(int argc, const char **argv, const char *prefix);
 extern int cmd_commit_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_count_objects(int argc, const char **argv, const char *prefix);
+extern int cmd_describe(int argc, const char **argv, const char *prefix);
 extern int cmd_diff_files(int argc, const char **argv, const char *prefix);
 extern int cmd_diff_index(int argc, const char **argv, const char *prefix);
 extern int cmd_diff(int argc, const char **argv, const char *prefix);
diff --git a/describe.c b/describe.c
deleted file mode 100644
index 3c2df03..0000000
--- a/describe.c
+++ /dev/null
@@ -1,176 +0,0 @@
-#include "cache.h"
-#include "commit.h"
-#include "tag.h"
-#include "refs.h"
-
-#define SEEN (1u << 0)
-
-static const char describe_usage[] =
-"git-describe [--all] [--tags] [--abbrev=<n>] <committish>*";
-
-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 names, allocs;
-static struct commit_name {
-	const struct commit *commit;
-	int prio; /* annotated tag = 2, tag = 1, head = 0 */
-	char path[FLEX_ARRAY]; /* more */
-} **name_array = NULL;
-
-static struct commit_name *match(struct commit *cmit)
-{
-	int i = names;
-	struct commit_name **p = name_array;
-
-	while (i-- > 0) {
-		struct commit_name *n = *p++;
-		if (n->commit == cmit)
-			return n;
-	}
-	return NULL;
-}
-
-static void add_to_known_names(const char *path,
-			       const struct commit *commit,
-			       int prio)
-{
-	int idx;
-	int len = strlen(path)+1;
-	struct commit_name *name = xmalloc(sizeof(struct commit_name) + len);
-
-	name->commit = commit;
-	name->prio = prio;
-	memcpy(name->path, path, len);
-	idx = names;
-	if (idx >= allocs) {
-		allocs = (idx + 50) * 3 / 2;
-		name_array = xrealloc(name_array, allocs*sizeof(*name_array));
-	}
-	name_array[idx] = name;
-	names = ++idx;
-}
-
-static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)
-{
-	struct commit *commit = lookup_commit_reference_gently(sha1, 1);
-	struct object *object;
-	int prio;
-
-	if (!commit)
-		return 0;
-	object = parse_object(sha1);
-	/* If --all, then any refs are used.
-	 * If --tags, then any tags are used.
-	 * Otherwise only annotated tags are used.
-	 */
-	if (!strncmp(path, "refs/tags/", 10)) {
-		if (object->type == OBJ_TAG)
-			prio = 2;
-		else
-			prio = 1;
-	}
-	else
-		prio = 0;
-
-	if (!all) {
-		if (!prio)
-			return 0;
-		if (!tags && prio < 2)
-			return 0;
-	}
-	add_to_known_names(all ? path + 5 : path + 10, commit, prio);
-	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;
-
-	if (a->prio != b->prio)
-		return b->prio - a->prio;
-	return (a_date > b_date) ? -1 : (a_date == b_date) ? 0 : 1;
-}
-
-static void describe(const char *arg, int last_one)
-{
-	unsigned char sha1[20];
-	struct commit *cmit;
-	struct commit_list *list;
-	static int initialized = 0;
-	struct commit_name *n;
-
-	if (get_sha1(arg, sha1))
-		die("Not a valid object name %s", arg);
-	cmit = lookup_commit_reference(sha1);
-	if (!cmit)
-		die("%s is not a valid '%s' object", arg, commit_type);
-
-	if (!initialized) {
-		initialized = 1;
-		for_each_ref(get_name, NULL);
-		qsort(name_array, names, sizeof(*name_array), compare_names);
-	}
-
-	n = match(cmit);
-	if (n) {
-		printf("%s\n", n->path);
-		return;
-	}
-
-	list = NULL;
-	commit_list_insert(cmit, &list);
-	while (list) {
-		struct commit *c = pop_most_recent_commit(&list, SEEN);
-		n = match(c);
-		if (n) {
-			printf("%s-g%s\n", n->path,
-			       find_unique_abbrev(cmit->object.sha1, abbrev));
-			if (!last_one)
-				clear_commit_marks(cmit, SEEN);
-			return;
-		}
-	}
-	die("cannot describe '%s'", sha1_to_hex(cmit->object.sha1));
-}
-
-int main(int argc, char **argv)
-{
-	int i;
-
-	for (i = 1; i < argc; i++) {
-		const char *arg = argv[i];
-
-		if (*arg != '-')
-			break;
-		else if (!strcmp(arg, "--all"))
-			all = 1;
-		else if (!strcmp(arg, "--tags"))
-			tags = 1;
-		else if (!strncmp(arg, "--abbrev=", 9)) {
-			abbrev = strtoul(arg + 9, NULL, 10);
-			if (abbrev < MINIMUM_ABBREV || 40 < abbrev)
-				abbrev = DEFAULT_ABBREV;
-		}
-		else
-			usage(describe_usage);
-	}
-
-	setup_git_directory();
-	save_commit_buffer = 0;
-
-	if (argc <= i)
-		describe("HEAD", 1);
-	else
-		while (i < argc) {
-			describe(argv[i], (i == argc - 1));
-			i++;
-		}
-
-	return 0;
-}
diff --git a/git.c b/git.c
index e7bc79a..9a0185c 100644
--- a/git.c
+++ b/git.c
@@ -220,6 +220,7 @@ static void handle_internal_command(int argc, const char **argv, char **envp)
 		{ "cherry", cmd_cherry, RUN_SETUP },
 		{ "commit-tree", cmd_commit_tree, RUN_SETUP },
 		{ "count-objects", cmd_count_objects, RUN_SETUP },
+		{ "describe", cmd_describe, RUN_SETUP },
 		{ "diff", cmd_diff, RUN_SETUP | USE_PAGER },
 		{ "diff-files", cmd_diff_files, RUN_SETUP },
 		{ "diff-index", cmd_diff_index, RUN_SETUP },
-- 
1.4.4.4.gf027-dirty

[PATCH 3/3] Chose better tag names in git-describe after merges.

[Shawn O. Pearce]

Recently git.git itself encountered a situation on its master and
next branches where git-describe stopped reporting 'v1.5.0-rc0-gN'
and instead started reporting 'v1.4.4.4-gN'.  This appeared to be
a backward jump in version numbering.

  maint     o-------------------4
            \                    \
  master     o-o-o-o-o-o-o-5-o-C-o-W

The issue is that commit C in the diagram claims it is version
1.5.0, as the tag v1.5.0 is placed on commit 5.  Yet commit W
claims it is version 1.4.4.4 as the tag v1.5.0 has an older tag
date than the v1.4.4.4 tag.

As it turns out this situation is very common.  A bug fix applied
to maint and later merged into master occurs frequently enough that
it should Just Work Right(tm).

Rather than taking the first tag that gets found git-describe will
now generate a list of all possible tags and select the one which
has the most number of commits in common with HEAD (or whatever
revision the user requested the description of).

This rule is based on the principle shown in the diagram above.
There are a large number of commits on the primary development branch
'master' which do not appear in the 'maint' branch, and many of
these are already tagged as part of v1.5.0-rc0.  Additionally these
commits are not in v1.4.4.4, as they are part of the v1.5.0 release
still being developed.  The v1.5.0-rc0 tag is more descriptive of
W than v1.4.4.4 is, and therefore should be used.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---

 This implements the algorithm I suggested on the mailing list.

 In my limited testing on git.git its 4x slower than the previous
 git-describe on current 'next' as its coming up with about 10
 tags as possible matches and then needs to generate the rev-list
 for each of them.  (Old = 100 ms, new = 400 ms).  I think that is
 acceptable in exchange for a "more likely to be correct" answer,
 especially when users are embedding git-describe's output into
 their binaries and expecting it to make some sort of sense.

 Since this is my first foray into calling the revision machinary
 for any sort of useful computation I would certainly appreciate
 comments and suggestions for improvements from those who know it
 better than I.  :-)

 builtin-describe.c |   78 ++++++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 67 insertions(+), 11 deletions(-)

diff --git a/builtin-describe.c b/builtin-describe.c
index ad3b469..d65c7d2 100644
--- a/builtin-describe.c
+++ b/builtin-describe.c
@@ -2,10 +2,11 @@
 #include "commit.h"
 #include "tag.h"
 #include "refs.h"
+#include "diff.h"
+#include "diffcore.h"
+#include "revision.h"
 #include "builtin.h"
 
-#define SEEN (1u << 0)
-
 static const char describe_usage[] =
 "git-describe [--all] [--tags] [--abbrev=<n>] <committish>*";
 
@@ -16,7 +17,7 @@ static int abbrev = DEFAULT_ABBREV;
 
 static int names, allocs;
 static struct commit_name {
-	const struct commit *commit;
+	struct commit *commit;
 	int prio; /* annotated tag = 2, tag = 1, head = 0 */
 	char path[FLEX_ARRAY]; /* more */
 } **name_array = NULL;
@@ -35,7 +36,7 @@ static struct commit_name *match(struct commit *cmit)
 }
 
 static void add_to_known_names(const char *path,
-			       const struct commit *commit,
+			       struct commit *commit,
 			       int prio)
 {
 	int idx;
@@ -98,6 +99,12 @@ static int compare_names(const void *_a, const void *_b)
 	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;
+};
+
 static void describe(const char *arg, int last_one)
 {
 	unsigned char sha1[20];
@@ -105,6 +112,7 @@ static void describe(const char *arg, int last_one)
 	struct commit_list *list;
 	static int initialized = 0;
 	struct commit_name *n;
+	struct possible_tag *all_matches, *min_match, *cur_match;
 
 	if (get_sha1(arg, sha1))
 		die("Not a valid object name %s", arg);
@@ -125,19 +133,67 @@ static void describe(const char *arg, int last_one)
 	}
 
 	list = NULL;
+	all_matches = NULL;
+	cur_match = NULL;
 	commit_list_insert(cmit, &list);
 	while (list) {
-		struct commit *c = pop_most_recent_commit(&list, SEEN);
+		struct commit *c = pop_commit(&list);
 		n = match(c);
 		if (n) {
-			printf("%s-g%s\n", n->path,
-			       find_unique_abbrev(cmit->object.sha1, abbrev));
-			if (!last_one)
-				clear_commit_marks(cmit, SEEN);
-			return;
+			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;
+		} else {
+			struct commit_list *parents = c->parents;
+			while (parents) {
+				struct commit *p = parents->item;
+				parse_commit(p);
+				if (!(p->object.flags & SEEN)) {
+					p->object.flags |= SEEN;
+					insert_by_date(p, &list);
+				}
+				parents = parents->next;
+			}
+		}
+	}
+
+	if (!all_matches)
+		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;
+
+		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)
+			min_match = cur_match;
+	}
+	printf("%s-g%s\n", min_match->name->path,
+		   find_unique_abbrev(cmit->object.sha1, abbrev));
+
+	if (!last_one) {
+		for (cur_match = all_matches; cur_match; cur_match = min_match) {
+			min_match = cur_match->next;
+			free(cur_match);
 		}
+		clear_commit_marks(cmit, SEEN);
 	}
-	die("cannot describe '%s'", sha1_to_hex(cmit->object.sha1));
 }
 
 int cmd_describe(int argc, const char **argv, const char *prefix)
-- 
1.4.4.4.gf027-dirty