[PATCH 2/2] Correct priority of lightweight tags in git-describe.

[PATCH 2/2] Correct priority of lightweight tags in git-describe.

[Shawn O. Pearce]

We really want to always favor an annotated tag over a lightweight
tag when describing a commit.  Unfortunately git-describe wasn't
doing this as it was favoring the depth attribute of a possible_tag
over the priority.  Now priority is the highest sort and we only
consider a lightweight tag if no annotated tags were identified.

Rather than searching for the minimum tag using a simple loop we
now sort them using a stable sort algorithm, this way the possible
tags display in order if --debug gets used.  The stable sort helps
to preseve the inherit topology/date order that we obtain during
our search loop.

This fix allows the tests in t6120-describe.sh to pass.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 builtin-describe.c |   30 +++++++++++++++++++-----------
 1 files changed, 19 insertions(+), 11 deletions(-)

diff --git a/builtin-describe.c b/builtin-describe.c
index 421658d..45fea10 100644
--- a/builtin-describe.c
+++ b/builtin-describe.c
@@ -22,6 +22,9 @@ static struct commit_name {
 	int prio; /* annotated tag = 2, tag = 1, head = 0 */
 	char path[FLEX_ARRAY]; /* more */
 } **name_array[256];
+static const char *prio_names[] = {
+	"head", "lightweight", "annotated",
+};
 
 static struct commit_name *match(struct commit *cmit)
 {
@@ -122,6 +125,17 @@ struct possible_tag {
 	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;
+	return 0;
+}
+
 static void describe(const char *arg, int last_one)
 {
 	unsigned char sha1[20];
@@ -129,7 +143,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[MAX_TAGS], *min_match;
+	struct possible_tag all_matches[MAX_TAGS];
 	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
 	unsigned long seen_commits = 0;
 
@@ -205,18 +219,12 @@ static void describe(const char *arg, int last_one)
 	if (!match_cnt)
 		die("cannot describe '%s'", sha1_to_hex(cmit->object.sha1));
 
-	min_match = &all_matches[0];
-	for (cur_match = 1; cur_match < match_cnt; cur_match++) {
-		struct possible_tag *t = &all_matches[cur_match];
-		if (t->depth < min_match->depth
-			&& t->name->prio >= min_match->name->prio)
-			min_match = t;
-	}
+	mergesort(all_matches, match_cnt, sizeof(all_matches[0]), compare_pt);
 	if (debug) {
 		for (cur_match = 0; cur_match < match_cnt; cur_match++) {
 			struct possible_tag *t = &all_matches[cur_match];
-			fprintf(stderr, " %c %8lu %s\n",
-				min_match == t ? '*' : ' ',
+			fprintf(stderr, " %-11s %8lu %s\n",
+				prio_names[t->name->prio],
 				t->depth, t->name->path);
 		}
 		fprintf(stderr, "traversed %lu commits\n", seen_commits);
@@ -228,7 +236,7 @@ static void describe(const char *arg, int last_one)
 				sha1_to_hex(gave_up_on->object.sha1));
 		}
 	}
-	printf("%s-g%s\n", min_match->name->path,
+	printf("%s-g%s\n", all_matches[0].name->path,
 		   find_unique_abbrev(cmit->object.sha1, abbrev));
 
 	if (!last_one)
-- 
1.5.0.rc1.g4494

Re: [PATCH 2/2] Correct priority of lightweight tags in git-describe.

[Junio C Hamano]

How about this on top?

 * We seem to do "a_" more often than "_a" for parameter names
   we type-cast.

 * int would be enough for 'depth', not long.  Also, "return
   (a->depth - b->depth)" is kosher only when it is signed,
   although it works in practice on sane platforms.

 * I did not find mergesort(); if we want stable, explicitly do
   so.  In practice, qsort() seems stable (as you know qsort()
   does not have to be implemented as quicksort).

--

diff --git a/builtin-describe.c b/builtin-describe.c
index 45fea10..e38c899 100644
--- a/builtin-describe.c
+++ b/builtin-describe.c
@@ -121,18 +121,21 @@ static int compare_names(const void *_a, const void *_b)
 
 struct possible_tag {
 	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)
+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;
+	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;
 }
 
@@ -146,6 +149,7 @@ static void describe(const char *arg, int last_one)
 	struct possible_tag all_matches[MAX_TAGS];
 	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
 	unsigned long seen_commits = 0;
+	int found = 0;
 
 	if (get_sha1(arg, sha1))
 		die("Not a valid object name %s", arg);
@@ -185,6 +189,7 @@ static void describe(const char *arg, int last_one)
 				t->name = n;
 				t->depth = seen_commits - 1;
 				t->flag_within = 1u << match_cnt;
+				t->found_order = found++;
 				c->object.flags |= t->flag_within;
 				if (n->prio == 2)
 					annotated_cnt++;
@@ -219,11 +224,11 @@ static void describe(const char *arg, int last_one)
 	if (!match_cnt)
 		die("cannot describe '%s'", sha1_to_hex(cmit->object.sha1));
 
-	mergesort(all_matches, match_cnt, sizeof(all_matches[0]), compare_pt);
+	qsort(all_matches, match_cnt, sizeof(all_matches[0]), compare_pt);
 	if (debug) {
 		for (cur_match = 0; cur_match < match_cnt; cur_match++) {
 			struct possible_tag *t = &all_matches[cur_match];
-			fprintf(stderr, " %-11s %8lu %s\n",
+			fprintf(stderr, " %-11s %8d %s\n",
 				prio_names[t->name->prio],
 				t->depth, t->name->path);
 		}

Re: [PATCH 2/2] Correct priority of lightweight tags in git-describe.

[Shawn O. Pearce]

Junio C Hamano <junkio@cox.net> wrote:
> How about this on top?
> 
>  * We seem to do "a_" more often than "_a" for parameter names
>    we type-cast.

I copied the header from the compare_names routine in
builtin-describe.c.  Maybe apply this too?

-- >8 --
diff --git a/builtin-describe.c b/builtin-describe.c
index e38c899..e514bc3 100644
--- a/builtin-describe.c
+++ b/builtin-describe.c
@@ -104,10 +104,10 @@ 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)
+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;
+	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);
-- <8 --

>  * int would be enough for 'depth', not long.  Also, "return
>    (a->depth - b->depth)" is kosher only when it is signed,
>    although it works in practice on sane platforms.

I originally went with unsigned long as that matches the size
of a packfile, and I wasn't using depth in a signed way.  Until
that patch.  Good catch.

>  * I did not find mergesort(); if we want stable, explicitly do
>    so.  In practice, qsort() seems stable (as you know qsort()
>    does not have to be implemented as quicksort).

Must be a *BSD extension.  Oops.


Patch looked good.  Thanks.

-- 
Shawn.