[PATCH v3] tag: support --sort=<spec>

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

--sort=version:refname (or --sort=v:refname for short) sorts tags as
if they are versions. --sort=-refname reverses the order (with or
without ":version").

versioncmp() is copied from string/strverscmp.c in glibc commit
ee9247c38a8def24a59eb5cfb7196a98bef8cfdc, reformatted to Git coding
style. The implementation is under LGPL-2.1 and according to [1] I can
relicense it to GPLv2.

[1] http://www.gnu.org/licenses/gpl-faq.html#AllCompatibility

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 v3 tweaks the sorting syntax a bit (version:refname vs refname:version)
 and embed strverscmp() to git code (instead of relying on one from glibc).

 Documentation/git-tag.txt |  6 ++++
 Makefile                  |  1 +
 builtin/tag.c             | 68 ++++++++++++++++++++++++++++++++++---
 cache.h                   |  2 ++
 t/t7004-tag.sh            | 43 ++++++++++++++++++++++++
 versioncmp.c (new)        | 85 +++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 200 insertions(+), 5 deletions(-)

diff --git a/Documentation/git-tag.txt b/Documentation/git-tag.txt
index 404257d..9b05931 100644
--- a/Documentation/git-tag.txt
+++ b/Documentation/git-tag.txt
@@ -95,6 +95,12 @@ OPTIONS
 	using fnmatch(3)).  Multiple patterns may be given; if any of
 	them matches, the tag is shown.
 
+--sort=<type>::
+	Sort in a specific order. Supported type is "refname"
+	(lexicographic order), "version:refname" or "v:refname" (tags
+	name are treated as versions). Prepend "-" to reverse sort
+	order.
+
 --column[=<options>]::
 --no-column::
 	Display tag listing in columns. See configuration variable
diff --git a/Makefile b/Makefile
index dddaf4f..16b00a5 100644
--- a/Makefile
+++ b/Makefile
@@ -884,6 +884,7 @@ LIB_OBJS += userdiff.o
 LIB_OBJS += utf8.o
 LIB_OBJS += varint.o
 LIB_OBJS += version.o
+LIB_OBJS += versioncmp.o
 LIB_OBJS += walker.o
 LIB_OBJS += wildmatch.o
 LIB_OBJS += wrapper.o
diff --git a/builtin/tag.c b/builtin/tag.c
index 74d3780..73b8a24 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -27,9 +27,16 @@ static const char * const git_tag_usage[] = {
 	NULL
 };
 
+#define STRCMP_SORT     0	/* must be zero */
+#define VERCMP_SORT     1
+#define SORT_MASK       0x7fff
+#define REVERSE_SORT    0x8000
+
 struct tag_filter {
 	const char **patterns;
 	int lines;
+	int sort;
+	struct string_list tags;
 	struct commit_list *with_commit;
 };
 
@@ -166,7 +173,10 @@ static int show_reference(const char *refname, const unsigned char *sha1,
 			return 0;
 
 		if (!filter->lines) {
-			printf("%s\n", refname);
+			if (filter->sort)
+				string_list_append(&filter->tags, refname);
+			else
+				printf("%s\n", refname);
 			return 0;
 		}
 		printf("%-15s ", refname);
@@ -177,17 +187,39 @@ static int show_reference(const char *refname, const unsigned char *sha1,
 	return 0;
 }
 
+static int sort_by_version(const void *a_, const void *b_)
+{
+	const struct string_list_item *a = a_;
+	const struct string_list_item *b = b_;
+	return versioncmp(a->string, b->string);
+}
+
 static int list_tags(const char **patterns, int lines,
-			struct commit_list *with_commit)
+		     struct commit_list *with_commit, int sort)
 {
 	struct tag_filter filter;
 
 	filter.patterns = patterns;
 	filter.lines = lines;
+	filter.sort = sort;
 	filter.with_commit = with_commit;
+	memset(&filter.tags, 0, sizeof(filter.tags));
+	filter.tags.strdup_strings = 1;
 
 	for_each_tag_ref(show_reference, (void *) &filter);
-
+	if (sort) {
+		int i;
+		if ((sort & SORT_MASK) == VERCMP_SORT)
+			qsort(filter.tags.items, filter.tags.nr,
+			      sizeof(struct string_list_item), sort_by_version);
+		if (sort & REVERSE_SORT)
+			for (i = filter.tags.nr - 1; i >= 0; i--)
+				printf("%s\n", filter.tags.items[i].string);
+		else
+			for (i = 0; i < filter.tags.nr; i++)
+				printf("%s\n", filter.tags.items[i].string);
+		string_list_clear(&filter.tags, 0);
+	}
 	return 0;
 }
 
@@ -427,6 +459,26 @@ static int parse_opt_points_at(const struct option *opt __attribute__((unused)),
 	return 0;
 }
 
+static int parse_opt_sort(const struct option *opt, const char *arg, int unset)
+{
+	int *sort = opt->value;
+	if (*arg == '-') {
+		*sort = REVERSE_SORT;
+		arg++;
+	} else
+		*sort = STRCMP_SORT;
+	if (starts_with(arg, "version:")) {
+		*sort |= VERCMP_SORT;
+		arg += 8;
+	} else if (starts_with(arg, "v:")) {
+		*sort |= VERCMP_SORT;
+		arg += 2;
+	}
+	if (strcmp(arg, "refname"))
+		die(_("unsupported sort specification %s"), arg);
+	return 0;
+}
+
 int cmd_tag(int argc, const char **argv, const char *prefix)
 {
 	struct strbuf buf = STRBUF_INIT;
@@ -437,7 +489,7 @@ int cmd_tag(int argc, const char **argv, const char *prefix)
 	struct create_tag_options opt;
 	char *cleanup_arg = NULL;
 	int annotate = 0, force = 0, lines = -1;
-	int cmdmode = 0;
+	int cmdmode = 0, sort = 0;
 	const char *msgfile = NULL, *keyid = NULL;
 	struct msg_arg msg = { 0, STRBUF_INIT };
 	struct commit_list *with_commit = NULL;
@@ -462,6 +514,10 @@ int cmd_tag(int argc, const char **argv, const char *prefix)
 					N_("use another key to sign the tag")),
 		OPT__FORCE(&force, N_("replace the tag if exists")),
 		OPT_COLUMN(0, "column", &colopts, N_("show tag list in columns")),
+		{
+			OPTION_CALLBACK, 0, "sort", &sort, N_("type"), N_("sort tags"),
+			PARSE_OPT_NONEG, parse_opt_sort
+		},
 
 		OPT_GROUP(N_("Tag listing options")),
 		{
@@ -509,7 +565,9 @@ int cmd_tag(int argc, const char **argv, const char *prefix)
 			copts.padding = 2;
 			run_column_filter(colopts, &copts);
 		}
-		ret = list_tags(argv, lines == -1 ? 0 : lines, with_commit);
+		if (lines != -1 && sort)
+			die(_("--sort and -n are incompatible"));
+		ret = list_tags(argv, lines == -1 ? 0 : lines, with_commit, sort);
 		if (column_active(colopts))
 			stop_column_filter();
 		return ret;
diff --git a/cache.h b/cache.h
index dc040fb..082a783 100644
--- a/cache.h
+++ b/cache.h
@@ -1367,4 +1367,6 @@ int stat_validity_check(struct stat_validity *sv, const char *path);
  */
 void stat_validity_update(struct stat_validity *sv, int fd);
 
+int versioncmp(const char *s1, const char *s2);
+
 #endif /* CACHE_H */
diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index c8d6e9f..143a8ea 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -1380,4 +1380,47 @@ test_expect_success 'multiple --points-at are OR-ed together' '
 	test_cmp expect actual
 '
 
+test_expect_success 'lexical sort' '
+	git tag foo1.3 &&
+	git tag foo1.6 &&
+	git tag foo1.10 &&
+	git tag -l --sort=refname "foo*" >actual &&
+	cat >expect <<EOF &&
+foo1.10
+foo1.3
+foo1.6
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'version sort' '
+	git tag -l --sort=version:refname "foo*" >actual &&
+	cat >expect <<EOF &&
+foo1.3
+foo1.6
+foo1.10
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'reverse version sort' '
+	git tag -l --sort=-version:refname "foo*" >actual &&
+	cat >expect <<EOF &&
+foo1.10
+foo1.6
+foo1.3
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'reverse lexical sort' '
+	git tag -l --sort=-refname "foo*" >actual &&
+	cat >expect <<EOF &&
+foo1.6
+foo1.3
+foo1.10
+EOF
+	test_cmp expect actual
+'
+
 test_done
diff --git a/versioncmp.c b/versioncmp.c
new file mode 100644
index 0000000..18a9632
--- /dev/null
+++ b/versioncmp.c
@@ -0,0 +1,85 @@
+#include "git-compat-util.h"
+
+/*
+ * states: S_N: normal, S_I: comparing integral part, S_F: comparing
+ * fractionnal parts, S_Z: idem but with leading Zeroes only
+ */
+#define  S_N    0x0
+#define  S_I    0x3
+#define  S_F    0x6
+#define  S_Z    0x9
+
+/* result_type: CMP: return diff; LEN: compare using len_diff/diff */
+#define  CMP    2
+#define  LEN    3
+
+
+/*
+ * Compare S1 and S2 as strings holding indices/version numbers,
+ * returning less than, equal to or greater than zero if S1 is less
+ * than, equal to or greater than S2 (for more info, see the texinfo
+ * doc).
+ */
+
+int versioncmp(const char *s1, const char *s2)
+{
+	const unsigned char *p1 = (const unsigned char *) s1;
+	const unsigned char *p2 = (const unsigned char *) s2;
+
+	/*
+	 * Symbol(s)    0       [1-9]   others
+	 * Transition   (10) 0  (01) d  (00) x
+	 */
+	static const uint8_t next_state[] = {
+		/* state    x    d    0  */
+		/* S_N */  S_N, S_I, S_Z,
+		/* S_I */  S_N, S_I, S_I,
+		/* S_F */  S_N, S_F, S_F,
+		/* S_Z */  S_N, S_F, S_Z
+	};
+
+	static const int8_t result_type[] = {
+		/* state   x/x  x/d  x/0  d/x  d/d  d/0  0/x  0/d  0/0  */
+
+		/* S_N */  CMP, CMP, CMP, CMP, LEN, CMP, CMP, CMP, CMP,
+		/* S_I */  CMP, -1,  -1,  +1,  LEN, LEN, +1,  LEN, LEN,
+		/* S_F */  CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP,
+		/* S_Z */  CMP, +1,  +1,  -1,  CMP, CMP, -1,  CMP, CMP
+	};
+
+	if (p1 == p2)
+		return 0;
+
+	unsigned char c1 = *p1++;
+	unsigned char c2 = *p2++;
+	/* Hint: '0' is a digit too.  */
+	int state = S_N + ((c1 == '0') + (isdigit (c1) != 0));
+
+	int diff;
+	while ((diff = c1 - c2) == 0) {
+		if (c1 == '\0')
+			return diff;
+
+		state = next_state[state];
+		c1 = *p1++;
+		c2 = *p2++;
+		state += (c1 == '0') + (isdigit (c1) != 0);
+	}
+
+	state = result_type[state * 3 + (((c2 == '0') + (isdigit (c2) != 0)))];
+
+	switch (state) {
+	case CMP:
+		return diff;
+
+	case LEN:
+		while (isdigit (*p1++))
+			if (!isdigit (*p2++))
+				return 1;
+
+		return isdigit (*p2) ? -1 : diff;
+
+	default:
+		return state;
+	}
+}
-- 
1.9.0.40.gaa8c3ea