Add a "git-describe" command

@@ -135,7 +135,8 @@ PROGRAMS = \
 	git-unpack-objects$X git-update-index$X git-update-server-info$X \
 	git-upload-pack$X git-verify-pack$X git-write-tree$X \
 	git-update-ref$X git-symbolic-ref$X git-check-ref-format$X \
-	git-name-rev$X git-pack-redundant$X git-repo-config$X git-var$X
+	git-name-rev$X git-pack-redundant$X git-repo-config$X git-var$X \
+	git-describe$X
 
 # what 'all' will build and 'install' will install.
 ALL_PROGRAMS = $(PROGRAMS) $(SIMPLE_PROGRAMS) $(SCRIPTS) git$X

@@ -0,0 +1,118 @@
+#include "cache.h"
+#include "commit.h"
+#include "refs.h"
+
+#define SEEN (1u << 0)
+
+static const char describe_usage[] = "git-describe [--all] <committish>*";
+
+static int all = 0;	/* Default to tags only */
+
+static int names = 0, allocs = 0;
+static struct commit_name {
+	const struct commit *commit;
+	char path[];
+} **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 idx;
+	int len = strlen(path)+1;
+	struct commit_name *name = xmalloc(sizeof(struct commit_name) + len);
+
+	name->commit = commit;
+	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)
+{
+	struct commit *commit = lookup_commit_reference_gently(sha1, 1);
+	if (!commit)
+		return 0;
+	if (!all && strncmp(path, "refs/tags/", 10))
+		return 0;
+	add_to_known_names(path, commit);
+	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;
+	return (a_date > b_date) ? -1 : (a_date == b_date) ? 0 : 1;
+}
+
+static void describe(struct commit *cmit)
+{
+	struct commit_list *list;
+	static int initialized = 0;
+	struct commit_name *n;
+
+	if (!initialized) {
+		initialized = 1;
+		for_each_ref(get_name);
+		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%.8s\n", n->path, sha1_to_hex(cmit->object.sha1));
+			return;
+		}
+	}
+}
+
+int main(int argc, char **argv)
+{
+	int i;
+
+	for (i = 1; i < argc; i++) {
+		const char *arg = argv[i];
+		unsigned char sha1[20];
+		struct commit *cmit;
+
+		if (!strcmp(arg, "--all")) {
+			all = 1;
+			continue;
+		}
+		if (get_sha1(arg, sha1) < 0)
+			usage(describe_usage);
+		cmit = lookup_commit_reference(sha1);
+		if (!cmit)
+			usage(describe_usage);
+		describe(cmit);
+	}
+	return 0;
+}

@@ -55,7 +55,7 @@ all:
 # Define USE_STDEV below if you want git to care about the underlying device
 # change being considered an inode change from the update-cache perspective.
 
-GIT_VERSION = 1.0.GIT
+GIT_VERSION = $(shell git-describe HEAD | sed 's:refs/tags/::')
 
 # CFLAGS and LDFLAGS are for the users to override from the command line.
 

@@ -5,9 +5,14 @@
 
 #define SEEN (1u << 0)
 
-static const char describe_usage[] = "git-describe [--all] <committish>*";
+static const char describe_usage[] =
+"git-describe [--all] [--tags] [--abbrev=<n>] <committish>*";
 
 static int all = 0;	/* Default to annotated tags only */
+static int tags = 0;	/* But allow any tags if --tags is specified */
+
+#define DEFAULT_ABBREV 8 /* maybe too many */
+static int abbrev = DEFAULT_ABBREV;
 
 static int names = 0, allocs = 0;
 static struct commit_name {

@@ -50,13 +55,19 @@ static int get_name(const char *path, co
 	struct commit *commit = lookup_commit_reference_gently(sha1, 1);
 	if (!commit)
 		return 0;
+	/* If --all, then any refs are used.
+	 * If --tags, then any tags are used.
+	 * Otherwise only annotated tags are used.
+	 */
 	if (!all) {
-		struct object *object;
 		if (strncmp(path, "refs/tags/", 10))
 			return 0;
-		object = parse_object(sha1);
-		if (object->type != tag_type)
-			return 0;
+		if (!tags) {
+			struct object *object;
+			object = parse_object(sha1);
+			if (object->type != tag_type)
+				return 0;
+		}
 	}
 	add_to_known_names(all ? path : path + 10, commit);
 	return 0;

@@ -96,7 +107,7 @@ static void describe(struct commit *cmit
 		n = match(c);
 		if (n) {
 			printf("%s-g%s\n", n->path,
-			       find_unique_abbrev(cmit->object.sha1, 8));
+			       find_unique_abbrev(cmit->object.sha1, abbrev));
 			return;
 		}
 	}

@@ -115,6 +126,16 @@ int main(int argc, char **argv)
 			all = 1;
 			continue;
 		}
+		if (!strcmp(arg, "--tags")) {
+			tags = 1;
+			continue;
+		}
+		if (!strncmp(arg, "--abbrev=", 9)) {
+			abbrev = strtoul(arg + 9, NULL, 10);
+			if (abbrev < 4 || 40 <= abbrev)
+				abbrev = DEFAULT_ABBREV;
+			continue;
+		}
 		if (get_sha1(arg, sha1) < 0)
 			usage(describe_usage);
 		cmit = lookup_commit_reference(sha1);

@@ -1,3 +1,4 @@
+GIT-VERSION-FILE
 git
 git-add
 git-am

@@ -0,0 +1,18 @@
+#!/bin/sh
+
+GVF=GIT-VERSION-FILE
+
+VN=$(git describe --abbrev=4 HEAD 2>/dev/null) || VN=v1.0.GIT
+VN=$(expr "$VN" : v'\(.*\)')
+if test -r $GVF
+then
+	VC=$(sed -e 's/^GIT_VERSION = //' <$GVF)
+else
+	VC=unset
+fi
+test "$VN" = "$VC" || {
+	echo >&2 "GIT_VERSION = $VN"
+	echo "GIT_VERSION = $VN" >$GVF
+}
+
+

@@ -55,7 +55,9 @@ all:
 # Define USE_STDEV below if you want git to care about the underlying device
 # change being considered an inode change from the update-cache perspective.
 
-GIT_VERSION = 1.0.GIT
+GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE
+	@sh ./GIT-VERSION-GEN
+-include GIT-VERSION-FILE
 
 # CFLAGS and LDFLAGS are for the users to override from the command line.
 

@@ -369,7 +371,7 @@ all: $(ALL_PROGRAMS)
 all:
 	$(MAKE) -C templates
 
-git$X: git.c $(LIB_FILE) Makefile
+git$X: git.c $(LIB_FILE) Makefile GIT-VERSION-FILE
 	$(CC) -DGIT_EXEC_PATH='"$(bindir)"' -DGIT_VERSION='"$(GIT_VERSION)"' \
 		$(CFLAGS) $(COMPAT_CFLAGS) -o $@ $(filter %.c,$^) $(LIB_FILE)
 

@@ -499,6 +501,7 @@ deb: dist
 ### Cleaning rules
 
 clean:
+	rm -f GIT-VERSION-FILE
 	rm -f *.o mozilla-sha1/*.o arm/*.o ppc/*.o compat/*.o $(LIB_FILE)
 	rm -f $(PROGRAMS) $(SIMPLE_PROGRAMS) git$X
 	rm -f $(filter-out gitk,$(SCRIPTS))

@@ -511,3 +514,6 @@ clean:
 	$(MAKE) -C templates clean
 	$(MAKE) -C t/ clean
 
+.PHONY: all install clean
+.PHONY: .FORCE-GIT-VERSION-FILE
+

@@ -1,12 +1,13 @@
 #include "cache.h"
 #include "commit.h"
+#include "tag.h"
 #include "refs.h"
 
 #define SEEN (1u << 0)
 
 static const char describe_usage[] = "git-describe [--all] <committish>*";
 
-static int all = 0;	/* Default to tags only */
+static int all = 0;	/* Default to annotated tags only */
 
 static int names = 0, allocs = 0;
 static struct commit_name {

@@ -49,9 +50,15 @@ static int get_name(const char *path, co
 	struct commit *commit = lookup_commit_reference_gently(sha1, 1);
 	if (!commit)
 		return 0;
-	if (!all && strncmp(path, "refs/tags/", 10))
-		return 0;
-	add_to_known_names(path, commit);
+	if (!all) {
+		struct object *object;
+		if (strncmp(path, "refs/tags/", 10))
+			return 0;
+		object = parse_object(sha1);
+		if (object->type != tag_type)
+			return 0;
+	}
+	add_to_known_names(all ? path : path + 10, commit);
 	return 0;
 }
 

@@ -95,7 +95,8 @@ static void describe(struct commit *cmit
 		struct commit *c = pop_most_recent_commit(&list, SEEN);
 		n = match(c);
 		if (n) {
-			printf("%s-g%.8s\n", n->path, sha1_to_hex(cmit->object.sha1));
+			printf("%s-g%s\n", n->path,
+			       find_unique_abbrev(cmit->object.sha1, 8));
 			return;
 		}
 	}

@@ -17,6 +17,7 @@ static int abbrev = DEFAULT_ABBREV;
 static int names = 0, allocs = 0;
 static struct commit_name {
 	const struct commit *commit;
+	int prio; /* annotated tag = 2, tag = 1, head = 0 */
 	char path[];
 } **name_array = NULL;
 

@@ -33,13 +34,16 @@ static struct commit_name *match(struct 
 	return NULL;
 }
 
-static void add_to_known_names(const char *path, const struct commit *commit)
+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) {

@@ -53,23 +57,32 @@ static void add_to_known_names(const cha
 static int get_name(const char *path, const unsigned char *sha1)
 {
 	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 == tag_type)
+			prio = 2;
+		else
+			prio = 1;
+	}
+	else
+		prio = 0;
+
 	if (!all) {
-		if (strncmp(path, "refs/tags/", 10))
+		if (!prio)
+			return 0;
+		if (!tags && prio < 2)
 			return 0;
-		if (!tags) {
-			struct object *object;
-			object = parse_object(sha1);
-			if (object->type != tag_type)
-				return 0;
-		}
 	}
-	add_to_known_names(all ? path : path + 10, commit);
+	add_to_known_names(all ? path + 5 : path + 10, commit, prio);
 	return 0;
 }
 

@@ -79,6 +92,9 @@ static int compare_names(const void *_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;
 }
 

@@ -0,0 +1,79 @@
+git-describe(1)
+===============
+
+NAME
+----
+git-describe - Show the most recent tag that is reachable from a commit.
+
+
+SYNOPSIS
+--------
+'git-describe' [--all] [--tags] [--abbrev=<n>] <committish>...
+
+DESCRIPTION
+-----------
+The command finds the most recent tag that is reachable from a
+commit, and if the commit itself is pointed at by the tag, shows
+the tag.  Otherwise, it suffixes the tag name with abbreviated
+object name of the commit.
+
+
+OPTIONS
+-------
+<committish>::
+	The object name of the comittish. 
+
+--all::
+	Instead of using only the annotated tags, use any ref
+	found in `.git/refs/`.
+
+--tags::
+	Instead of using only the annotated tags, use any tag
+	found in `.git/refs/tags`.
+
+--abbrev=<n>::
+	Instead of using the default 8 hexadecimal digits as the
+	abbreviated object name, use <n> digits.
+
+
+EXAMPLES
+--------
+
+With something like git.git current tree, I get:
+
+	[torvalds@g5 git]$ git-describe parent
+	v1.0.4-g2414721b
+
+i.e. the current head of my "parent" branch is based on v1.0.4,
+but since it has a few commits on top of that, it has added the
+git hash of the thing to the end: "-g" + 8-char shorthand for
+the commit `2414721b194453f058079d897d13c4e377f92dc6`.
+
+Doing a "git-describe" on a tag-name will just show the tag name:
+
+	[torvalds@g5 git]$ git-describe v1.0.4
+	v1.0.4
+
+With --all, the command can use branch heads as references, so
+the output shows the reference path as well:
+
+	[torvalds@g5 git]$ git describe --all --abbrev=4 v1.0.5^2
+	tags/v1.0.0-g975b
+
+	[torvalds@g5 git]$ git describe --all HEAD^
+	heads/lt/describe-g975b
+
+
+Author
+------
+Written by Linus Torvalds <torvalds@osdl.org>, but somewhat
+butchered by Junio C Hamano <junkio@cox.net>
+
+Documentation
+--------------
+Documentation by David Greaves, Junio C Hamano and the git-list <git@vger.kernel.org>.
+
+GIT
+---
+Part of the gitlink:git[7] suite
+

@@ -139,6 +139,9 @@ Interrogation commands
 gitlink:git-cat-file[1]::
 	Provide content or type/size information for repository objects.
 
+gitlink:git-describe[1]::
+	Show the most recent tag that is reachable from a commit.
+
 gitlink:git-diff-index[1]::
 	Compares content and mode of blobs between the index and repository.
 

@@ -5,19 +5,21 @@
 #include "refs.h"
 
 static const char name_rev_usage[] =
-	"git-name-rev [--tags] ( --all | --stdin | commitish [commitish...] )\n";
+	"git-name-rev [--tags] ( --all | --stdin | \n"
+	"                       [--inverse] commitish [commitish...] )\n";
 
 typedef struct rev_name {
 	const char *tip_name;
 	int merge_traversals;
 	int generation;
+	int distance;
 } rev_name;
 
 static long cutoff = LONG_MAX;
 
 static void name_rev(struct commit *commit,
 		const char *tip_name, int merge_traversals, int generation,
-		int deref)
+		int distance, int deref)
 {
 	struct rev_name *name = (struct rev_name *)commit->object.util;
 	struct commit_list *parents;

@@ -50,6 +52,7 @@ copy_data:
 		name->tip_name = tip_name;
 		name->merge_traversals = merge_traversals;
 		name->generation = generation;
+		name->distance = distance;
 	} else
 		return;
 

@@ -66,10 +69,10 @@ copy_data:
 				sprintf(new_name, "%s^%d", tip_name, parent_number);
 
 			name_rev(parents->item, new_name,
-				merge_traversals + 1 , 0, 0);
+				merge_traversals + 1 , 0, distance + 1, 0);
 		} else {
 			name_rev(parents->item, tip_name, merge_traversals,
-				generation + 1, 0);
+				generation + 1, distance + 1, 0);
 		}
 	}
 }

@@ -98,7 +101,7 @@ static int name_ref(const char *path, co
 		while ((p = strchr(path, '/')))
 			path = p+1;
 
-		name_rev(commit, strdup(path), 0, 0, deref);
+		name_rev(commit, strdup(path), 0, 0, 0, deref);
 	}
 	return 0;
 }

@@ -118,12 +121,56 @@ static const char* get_rev_name(struct o
 
 	return buffer;
 }
-	
+
+typedef struct {
+	const char* name;
+	struct object* o;
+} named_commit_t;
+static named_commit_t* ref_list = NULL;
+static int ref_count = 0;
+
+static int inverse_build_ref_list(const char *path, const unsigned char *sha1)
+{
+	struct object *o = deref_tag(parse_object(sha1), path, 0);
+
+	if ((!tags_only || !strncmp(path, "refs/tags/", 10)) &&
+			o->type == commit_type) {
+		struct commit* commit = (struct commit*)o;
+
+		if (cutoff > commit->date)
+			cutoff = commit->date;
+
+		if ((ref_count % 256) == 0)
+			ref_list = xrealloc(ref_list,
+				sizeof(named_commit_t*) * (ref_count + 256));
+		ref_list[ref_count].name = strdup(path);
+		ref_list[ref_count].o = (struct object*)commit;
+		ref_count++;
+	}
+	return 0;
+}
+
+static int name_comp(const void* a, const void* b)
+{
+	const rev_name* c = ((const named_commit_t*)a)->o->util;
+	const rev_name* d = ((const named_commit_t*)b)->o->util;
+
+	if (!c)
+		return 1;
+	if (!d)
+		return -1;
+	if (c->distance > d->distance)
+		return 1;
+	if (c->distance < d->distance)
+		return -1;
+	return 0;
+}
+
 int main(int argc, char **argv)
 {
 	struct object_list *revs = NULL;
 	struct object_list **walker = &revs;
-	int as_is = 0, all = 0, transform_stdin = 0;
+	int as_is = 0, all = 0, inverse = 0, transform_stdin = 0;
 
 	setup_git_directory();
 

@@ -142,6 +189,9 @@ int main(int argc, char **argv)
 			} else if (!strcmp(*argv, "--tags")) {
 				tags_only = 1;
 				continue;
+			} else if (!strcmp(*argv, "--inverse")) {
+				inverse = 1;
+				continue;
 			} else if (!strcmp(*argv, "--all")) {
 				if (argc > 1)
 					die("Specify either a list, or --all, not both!");

@@ -181,6 +231,27 @@ int main(int argc, char **argv)
 		walker = &((*walker)->next);
 	}
 
+	if (inverse) {
+		int i;
+
+		if (transform_stdin || all || !revs)
+			usage(name_rev_usage);
+
+		for_each_ref(inverse_build_ref_list);
+		
+		tags_only = 0;
+		for (; revs; revs = revs->next)
+			name_ref(revs->name, revs->item->sha1);
+
+		qsort(ref_list, ref_count, sizeof(named_commit_t), name_comp);
+
+		for (i = 0; i < ref_count; i++)
+			printf("%s %s\n", ref_list[i].name,
+				get_rev_name(ref_list[i].o));
+
+		return 0;
+	}
+
 	for_each_ref(name_ref);
 
 	if (transform_stdin) {