[PATCH] tag: support --sort=version

[PATCH] tag: support --sort=version

[Nguyễn Thái Ngọc Duy]

--sort=version sorts tags as versions. GNU extension's strverscmp is
used and no real compat implementation is provided so this is Linux only.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 I didn't know that coreutils' sort is simply a wrapper of strverscmp.
 With that GNU extension, implementing --sort is easy. Mac and Windows
 are welcome to reimplement strverscmp (of rip it off glibc).

 Documentation/git-tag.txt |  4 ++++
 builtin/tag.c             | 49 ++++++++++++++++++++++++++++++++++++++++++-----
 git-compat-util.h         |  7 +++++++
 3 files changed, 55 insertions(+), 5 deletions(-)

diff --git a/Documentation/git-tag.txt b/Documentation/git-tag.txt
index 404257d..fc23dc0 100644
--- a/Documentation/git-tag.txt
+++ b/Documentation/git-tag.txt
@@ -95,6 +95,10 @@ 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 "version". Prepend
+	"-" to revert sort order.
+
 --column[=<options>]::
 --no-column::
 	Display tag listing in columns. See configuration variable
diff --git a/builtin/tag.c b/builtin/tag.c
index 74d3780..db3567b 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -30,6 +30,8 @@ static const char * const git_tag_usage[] = {
 struct tag_filter {
 	const char **patterns;
 	int lines;
+	int version_sort;
+	struct string_list tags;
 	struct commit_list *with_commit;
 };
 
@@ -166,7 +168,10 @@ static int show_reference(const char *refname, const unsigned char *sha1,
 			return 0;
 
 		if (!filter->lines) {
-			printf("%s\n", refname);
+			if (filter->version_sort)
+				string_list_append(&filter->tags, refname);
+			else
+				printf("%s\n", refname);
 			return 0;
 		}
 		printf("%-15s ", refname);
@@ -177,17 +182,38 @@ 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 strverscmp(a->string, b->string);
+}
+
 static int list_tags(const char **patterns, int lines,
-			struct commit_list *with_commit)
+		     struct commit_list *with_commit, int version_sort)
 {
 	struct tag_filter filter;
 
 	filter.patterns = patterns;
 	filter.lines = lines;
+	filter.version_sort = version_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 (version_sort) {
+		int i;
+		qsort(filter.tags.items, filter.tags.nr,
+		      sizeof(struct string_list_item), sort_by_version);
+		if (version_sort > 0)
+			for (i = 0; i < filter.tags.nr; i++)
+				printf("%s\n", filter.tags.items[i].string);
+		else
+			for (i = filter.tags.nr - 1; i >= 0; i--)
+				printf("%s\n", filter.tags.items[i].string);
+		string_list_clear(&filter.tags, 0);
+	}
 	return 0;
 }
 
@@ -437,7 +463,8 @@ 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, version_sort = 0;
+	const char *sort = NULL;
 	const char *msgfile = NULL, *keyid = NULL;
 	struct msg_arg msg = { 0, STRBUF_INIT };
 	struct commit_list *with_commit = NULL;
@@ -462,6 +489,7 @@ 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")),
+		OPT_STRING(0, "sort", &sort, N_("type"), N_("sort tags")),
 
 		OPT_GROUP(N_("Tag listing options")),
 		{
@@ -509,7 +537,18 @@ 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 (sort) {
+			if (!strcmp(sort, "version"))
+				version_sort = 1;
+			else if (!strcmp(sort, "-version"))
+				version_sort = -1;
+			else
+				die(_("unsupported sort type %s"), sort);
+		}
+		if (lines != -1 && version_sort)
+			die(_("--sort and -l are incompatible"));
+		ret = list_tags(argv, lines == -1 ? 0 : lines, with_commit,
+				version_sort);
 		if (column_active(colopts))
 			stop_column_filter();
 		return ret;
diff --git a/git-compat-util.h b/git-compat-util.h
index cbd86c3..22089e9 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -721,4 +721,11 @@ void warn_on_inaccessible(const char *path);
 /* Get the passwd entry for the UID of the current process. */
 struct passwd *xgetpwuid_self(void);
 
+#ifndef __GNU_LIBRARY__
+static inline int strverscmp(const char *s1, const char *s2)
+{
+	die("strverscmp() not supported");
+}
+#endif
+
 #endif
-- 
1.9.0.40.gaa8c3ea

Re: [PATCH] tag: support --sort=version

[Jeff King]

On Wed, Feb 19, 2014 at 08:39:27PM +0700, Nguyễn Thái Ngọc Duy wrote:

> --sort=version sorts tags as versions. GNU extension's strverscmp is
> used and no real compat implementation is provided so this is Linux only.

Sounds like a good goal.

I wonder, if we were to merge the for-each-ref and tag
implementations[1], how this would integrate with for-each-ref's
sorting. It can sort on arbitrary fields like "--sort=-*authordate". I
think given the syntax you provide, this would fall out naturally as
just another key (albeit a slightly magical one, as it is building on
the %(refname:short) field but using a different comparator).

Would we ever want to version-sort any other field? Perhaps
%(content:subject) for a tag? I'm not sure what would be the most
natural way to specify that. Maybe "--sort=version:content:subject",
with just "--version" as a synonym for "version:refname:short".

We don't need to do any of that immediately.  This is mostly just me
thinking aloud, to make sure we do not paint ourselves into a corner
compatibility-wise.

-Peff

[1] I have patches which I really need to polish and send out that
    combine the ref-selection code (so tag, branch, and for-each-ref all
    know "--merged", "--contains", etc). I'd really like to combine the
    sorting and formatting code, too, so everybody can use "--sort" and
    "--format" with all of the associated fields.

Re: [PATCH] tag: support --sort=version

[Duy Nguyen]

On Wed, Feb 19, 2014 at 9:09 PM, Jeff King <peff@peff.net> wrote:
> On Wed, Feb 19, 2014 at 08:39:27PM +0700, Nguyễn Thái Ngọc Duy wrote:
>
>> --sort=version sorts tags as versions. GNU extension's strverscmp is
>> used and no real compat implementation is provided so this is Linux only.
>
> Sounds like a good goal.
>
> I wonder, if we were to merge the for-each-ref and tag
> implementations[1], how this would integrate with for-each-ref's
> sorting. It can sort on arbitrary fields like "--sort=-*authordate". I
> think given the syntax you provide, this would fall out naturally as
> just another key (albeit a slightly magical one, as it is building on
> the %(refname:short) field but using a different comparator).
>
> Would we ever want to version-sort any other field? Perhaps
> %(content:subject) for a tag? I'm not sure what would be the most
> natural way to specify that. Maybe "--sort=version:content:subject",
> with just "--version" as a synonym for "version:refname:short".

If f-e-r and tag share code and syntax then we could use another
letter for this sort type (like we use '-' to reverse sort order). I
think that would make the implementation easier as well. So we could
have --sort=.refname for version sorting refname, --sort=-.refname for
reversed version sort, and sort=-refname for reverse alphabetical
sort.

> We don't need to do any of that immediately.  This is mostly just me
> thinking aloud, to make sure we do not paint ourselves into a corner
> compatibility-wise.

Good thinking. If you plan to use the exact same sort syntax f-e-r
uses now, pick a letter (the dot I used above is probably not the
best), I'll rewrite this patch to use the same syntax.

>
> -Peff
>
> [1] I have patches which I really need to polish and send out that
>     combine the ref-selection code (so tag, branch, and for-each-ref all
>     know "--merged", "--contains", etc). I'd really like to combine the
>     sorting and formatting code, too, so everybody can use "--sort" and
>     "--format" with all of the associated fields.
-- 
Duy

Re: [PATCH] tag: support --sort=version

[Jeff King]

On Wed, Feb 19, 2014 at 09:19:24PM +0700, Duy Nguyen wrote:

> > We don't need to do any of that immediately.  This is mostly just me
> > thinking aloud, to make sure we do not paint ourselves into a corner
> > compatibility-wise.
> 
> Good thinking. If you plan to use the exact same sort syntax f-e-r
> uses now, pick a letter (the dot I used above is probably not the
> best), I'll rewrite this patch to use the same syntax.

I think I actually prefer the full word "version", as you have already.
It's clear what it means, and we can extend the syntax generally to:

  --sort=[-][comparison:]field

like:

  --sort=-version:subject

for descending version-sort by subject.  And then as a special-case
convenience, make "version" without a field default to
"version:refname". There's no ambiguity because the set of comparison
names and field-names is fixed, and we know there is no overlap.

If want to, we can _also_ give a one-letter abbreviation to the
comparison field, like:

  --sort=v:subject

but that is not necessary.

So I think your patch is fine as-is. It is perhaps a little funny to
start with the special case and only implement the general case later,
but:

  1. We would want the special case eventually, because it is the most
     natural thing to type, and pretty clearly the most common use-case.

  2. We may not ever even end up with the general case. This is just
     about making sure that if we _do_ add it, that it fits
     syntactically with "--sort=version".

-Peff

Re: [PATCH] tag: support --sort=version

[Duy Nguyen]

On Fri, Feb 21, 2014 at 3:43 AM, Jeff King <peff@peff.net> wrote:
> I think I actually prefer the full word "version", as you have already.
> It's clear what it means, and we can extend the syntax generally to:

Agreed. It's hard to find a letter that reminds you about "version".

>
>   --sort=[-][comparison:]field
>
> like:
>
>   --sort=-version:subject
>
> for descending version-sort by subject.  And then as a special-case
> convenience, make "version" without a field default to
> "version:refname". There's no ambiguity because the set of comparison
> names and field-names is fixed, and we know there is no overlap.
>
> If want to, we can _also_ give a one-letter abbreviation to the
> comparison field, like:
>
>   --sort=v:subject
>
> but that is not necessary.

Why not reversed order? So its syntax could be

[ "-" ] FIELD [ ":" [ "version" | "v" ] ]

It fits better to current f-e-r syntax where modifiers are after the
colon. And it avoids the possibility that someone adds field "version"
and we can't tell what "version" is what.
-- 
Duy

Re: [PATCH] tag: support --sort=version

[Junio C Hamano]

Duy Nguyen <pclouds@gmail.com> writes:

> Why not reversed order? So its syntax could be
>
> [ "-" ] FIELD [ ":" [ "version" | "v" ] ]
>
> It fits better to current f-e-r syntax where modifiers are after the
> colon. And it avoids the possibility that someone adds field "version"
> and we can't tell what "version" is what.

I think that reads well.

Re: [PATCH] tag: support --sort=version

[Jeff King]

On Fri, Feb 21, 2014 at 06:58:16PM +0700, Duy Nguyen wrote:

> >   --sort=[-][comparison:]field
> [...]
> Why not reversed order? So its syntax could be
> 
> [ "-" ] FIELD [ ":" [ "version" | "v" ] ]
> 
> It fits better to current f-e-r syntax where modifiers are after the
> colon. And it avoids the possibility that someone adds field "version"
> and we can't tell what "version" is what.

I find my version a bit more obvious, for two reasons:

  1. "version" here is not a modifier of the field name, it is a
     modifier of the sort. You cannot use it in non-sort contexts (like
     --format), and you cannot order it like other modifiers (you cannot
     say "refname:version:short", only "refname:short:version").

  2. There are actually two sort-modifiers: "-" for ordering, and then a
     comparator. In your proposal, they are split, whereas in mine, they
     are next to each other.

-Peff

Re: [PATCH] tag: support --sort=version

[Duy Nguyen]

On Sat, Feb 22, 2014 at 2:59 PM, Jeff King <peff@peff.net> wrote:
> On Fri, Feb 21, 2014 at 06:58:16PM +0700, Duy Nguyen wrote:
>
>> >   --sort=[-][comparison:]field
>> [...]
>> Why not reversed order? So its syntax could be
>>
>> [ "-" ] FIELD [ ":" [ "version" | "v" ] ]
>>
>> It fits better to current f-e-r syntax where modifiers are after the
>> colon. And it avoids the possibility that someone adds field "version"
>> and we can't tell what "version" is what.
>
> I find my version a bit more obvious, for two reasons:
>
>   1. "version" here is not a modifier of the field name, it is a
>      modifier of the sort. You cannot use it in non-sort contexts (like
>      --format), and you cannot order it like other modifiers (you cannot
>      say "refname:version:short", only "refname:short:version").

Or you can read it like "type cast this field as a version", where
sorting is affected but formatting, not so much. So you can specify it
with --format (but it's no-op, unless we find a fancy way to color
versions). I don't see a problem with accepting both
refname:version:short and refname:short:version in future for-each-ref
either. It will be the first time we accept multiple modifiers though.

>   2. There are actually two sort-modifiers: "-" for ordering, and then a
>      comparator. In your proposal, they are split, whereas in mine, they
>      are next to each other.
-- 
Duy

Re: [PATCH] tag: support --sort=version

[Eric Sunshine]

On Wed, Feb 19, 2014 at 8:39 AM, Nguyễn Thái Ngọc Duy <pclouds@gmail.com> wrote:
> --sort=version sorts tags as versions. GNU extension's strverscmp is
> used and no real compat implementation is provided so this is Linux only.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
> diff --git a/Documentation/git-tag.txt b/Documentation/git-tag.txt
> index 404257d..fc23dc0 100644
> --- a/Documentation/git-tag.txt
> +++ b/Documentation/git-tag.txt
> @@ -95,6 +95,10 @@ 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 "version". Prepend
> +       "-" to revert sort order.

s/revert/reverse/

> +
>  --column[=<options>]::
>  --no-column::
>         Display tag listing in columns. See configuration variable

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

[Nguyễn Thái Ngọc Duy]

--sort=refname:version (or --sort=refname:v for short) sorts tags as
if they are versions. --sort=-refname reverses the order (with or
without ":version"). This syntax is chosen to make it compatible with
future extension in "for-each-ref --sort"

GNU extension strverscmp is used so this is Linux only. Mac and
Windows will need to bundle a compat implementation (and long term we
may want to use compat version only so we can make XXX-rc, XXX-pre...
appear before XXX)

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 The new prereq GNULINUX is an ugly workaround until people provide
 strverscmp compat implementation. I hope that will happen soon as
 strverscmp.c does not look very complex.

 Documentation/git-tag.txt |  6 +++++
 builtin/tag.c             | 69 +++++++++++++++++++++++++++++++++++++++++++----
 git-compat-util.h         |  7 +++++
 t/t7004-tag.sh            | 43 +++++++++++++++++++++++++++++
 t/test-lib.sh             |  2 ++
 5 files changed, 122 insertions(+), 5 deletions(-)

diff --git a/Documentation/git-tag.txt b/Documentation/git-tag.txt
index 404257d..d8633bb 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"
+	(lexical order), "refname:version" or "refname:v" (tag names
+	are treated as version strings). Prepend "-" to reverse sorting
+	order.
+
 --column[=<options>]::
 --no-column::
 	Display tag listing in columns. See configuration variable
diff --git a/builtin/tag.c b/builtin/tag.c
index 74d3780..483d293 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 STRVERSCMP_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 strverscmp(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) == STRVERSCMP_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,27 @@ 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, "refname") ||
+	    (arg[7] != ':' && arg[7] != '\0'))
+		die(_("unsupported sort field %s"), arg);
+	if (arg[7] == ':') {
+		const char *modifier = arg + 8;
+		if (!strcmp(modifier, "version") || !strcmp(modifier, "v"))
+			*sort |= STRVERSCMP_SORT;
+		else
+			die(_("unsupported modifier %s"), modifier);
+	}
+	return 0;
+}
+
 int cmd_tag(int argc, const char **argv, const char *prefix)
 {
 	struct strbuf buf = STRBUF_INIT;
@@ -437,7 +490,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 +515,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 +566,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/git-compat-util.h b/git-compat-util.h
index cbd86c3..22089e9 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -721,4 +721,11 @@ void warn_on_inaccessible(const char *path);
 /* Get the passwd entry for the UID of the current process. */
 struct passwd *xgetpwuid_self(void);
 
+#ifndef __GNU_LIBRARY__
+static inline int strverscmp(const char *s1, const char *s2)
+{
+	die("strverscmp() not supported");
+}
+#endif
+
 #endif
diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index c8d6e9f..0b7b170 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 GNULINUX '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 GNULINUX 'version sort' '
+	git tag -l --sort=refname:version "foo*" >actual &&
+	cat >expect <<EOF &&
+foo1.3
+foo1.6
+foo1.10
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success GNULINUX 'reverse version sort' '
+	git tag -l --sort=-refname:version "foo*" >actual &&
+	cat >expect <<EOF &&
+foo1.10
+foo1.6
+foo1.3
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success GNULINUX '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/t/test-lib.sh b/t/test-lib.sh
index 1531c24..5e8c39a 100644
--- a/t/test-lib.sh
+++ b/t/test-lib.sh
@@ -771,6 +771,8 @@ case $(uname -s) in
 	;;
 esac
 
+[ "$(uname -o)" = "GNU/Linux" ] && test_set_prereq GNULINUX
+
 ( COLUMNS=1 && test $COLUMNS = 1 ) && test_set_prereq COLUMNS_CAN_BE_1
 test -z "$NO_PERL" && test_set_prereq PERL
 test -z "$NO_PYTHON" && test_set_prereq PYTHON
-- 
1.9.0.40.gaa8c3ea

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

[Jeff King]

On Sat, Feb 22, 2014 at 10:29:22AM +0700, Nguyễn Thái Ngọc Duy wrote:

> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  The new prereq GNULINUX is an ugly workaround until people provide
>  strverscmp compat implementation. I hope that will happen soon as
>  strverscmp.c does not look very complex.

Should GNULINUX be called HAVE_STRVERSCMP in the Makefile?

Then this:

> --- a/git-compat-util.h
> +++ b/git-compat-util.h
> @@ -721,4 +721,11 @@ void warn_on_inaccessible(const char *path);
>  /* Get the passwd entry for the UID of the current process. */
>  struct passwd *xgetpwuid_self(void);
>  
> +#ifndef __GNU_LIBRARY__
> +static inline int strverscmp(const char *s1, const char *s2)
> +{
> +	die("strverscmp() not supported");
> +}
> +#endif

becomes "#ifndef HAVE_STRVERSCMP", and this:

> diff --git a/t/test-lib.sh b/t/test-lib.sh
> index 1531c24..5e8c39a 100644
> --- a/t/test-lib.sh
> +++ b/t/test-lib.sh
> @@ -771,6 +771,8 @@ case $(uname -s) in
>  	;;
>  esac
>  
> +[ "$(uname -o)" = "GNU/Linux" ] && test_set_prereq GNULINUX
> +

can pick up the value from GIT-BUILD-OPTIONS as a prerequisite (see the
way we handle NO_PERL for an example). Though if we can just grab the
glibc version as a fallback, we can do away with that completely.

-Peff

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

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Sat, Feb 22, 2014 at 10:29:22AM +0700, Nguyễn Thái Ngọc Duy wrote:
>
>> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
>> ---
>>  The new prereq GNULINUX is an ugly workaround until people provide
>>  strverscmp compat implementation. I hope that will happen soon as
>>  strverscmp.c does not look very complex.
>
> Should GNULINUX be called HAVE_STRVERSCMP in the Makefile?
>
> Then this:
>
>> --- a/git-compat-util.h
>> +++ b/git-compat-util.h
>> @@ -721,4 +721,11 @@ void warn_on_inaccessible(const char *path);
>>  /* Get the passwd entry for the UID of the current process. */
>>  struct passwd *xgetpwuid_self(void);
>>  
>> +#ifndef __GNU_LIBRARY__
>> +static inline int strverscmp(const char *s1, const char *s2)
>> +{
>> +	die("strverscmp() not supported");
>> +}
>> +#endif
>
> becomes "#ifndef HAVE_STRVERSCMP", and this:
>
>> diff --git a/t/test-lib.sh b/t/test-lib.sh
>> index 1531c24..5e8c39a 100644
>> --- a/t/test-lib.sh
>> +++ b/t/test-lib.sh
>> @@ -771,6 +771,8 @@ case $(uname -s) in
>>  	;;
>>  esac
>>  
>> +[ "$(uname -o)" = "GNU/Linux" ] && test_set_prereq GNULINUX
>> +
>
> can pick up the value from GIT-BUILD-OPTIONS as a prerequisite (see the
> way we handle NO_PERL for an example). Though if we can just grab the
> glibc version as a fallback, we can do away with that completely.

;-)  I like that.

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

[Duy Nguyen]

On Mon, Feb 24, 2014 at 11:39 PM, Junio C Hamano <gitster@pobox.com> wrote:
>>> diff --git a/t/test-lib.sh b/t/test-lib.sh
>>> index 1531c24..5e8c39a 100644
>>> --- a/t/test-lib.sh
>>> +++ b/t/test-lib.sh
>>> @@ -771,6 +771,8 @@ case $(uname -s) in
>>>      ;;
>>>  esac
>>>
>>> +[ "$(uname -o)" = "GNU/Linux" ] && test_set_prereq GNULINUX
>>> +
>>
>> can pick up the value from GIT-BUILD-OPTIONS as a prerequisite (see the
>> way we handle NO_PERL for an example). Though if we can just grab the
>> glibc version as a fallback, we can do away with that completely.
>
> ;-)  I like that.
>

Jeff, I'm still waiting if you agree to go with this syntax or put
version before refname before rerolling (either with build time option
like this, or implement the compat function myself).
-- 
Duy

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

[Jeff King]

On Tue, Feb 25, 2014 at 06:30:35AM +0700, Duy Nguyen wrote:

> >>> +[ "$(uname -o)" = "GNU/Linux" ] && test_set_prereq GNULINUX
> >>> +
> >>
> >> can pick up the value from GIT-BUILD-OPTIONS as a prerequisite (see the
> >> way we handle NO_PERL for an example). Though if we can just grab the
> >> glibc version as a fallback, we can do away with that completely.
> >
> > ;-)  I like that.
> >
> 
> Jeff, I'm still waiting if you agree to go with this syntax or put
> version before refname before rerolling (either with build time option
> like this, or implement the compat function myself).

Sorry. I didn't respond because I was trying to think of something to
say besides "no, I still like mine better". I admit that it's mostly a
gut feeling, and I don't have any argument beyond what I've already
made (your "it's like a typecast" does make some sense, but I think that
is a convoluted way of thinking about it).

-Peff

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

[Nguyễn Thái Ngọc Duy]

--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

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

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> 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.

I'd propose this trivial change squashed in to record the above
in the file in question.

Thanks.

diff --git a/versioncmp.c b/versioncmp.c
index 18a9632..8f5a388 100644
--- a/versioncmp.c
+++ b/versioncmp.c
@@ -1,6 +1,13 @@
 #include "git-compat-util.h"
 
 /*
+ * versioncmp(): copied from string/strverscmp.c in glibc commit
+ * ee9247c38a8def24a59eb5cfb7196a98bef8cfdc, reformatted to Git coding
+ * style. The implementation is under LGPL-2.1 and Git relicenses it
+ * to GPLv2.
+ */
+
+/*
  * states: S_N: normal, S_I: comparing integral part, S_F: comparing
  * fractionnal parts, S_Z: idem but with leading Zeroes only
  */

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

[Jeff King]

On Tue, Feb 25, 2014 at 07:22:15PM +0700, Nguyễn Thái Ngọc Duy wrote:

> 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.

Cool. I think doing this makes the most sense, as we do not have to
worry about build-time config (and I do not see any particular reason
why we would want to use the system strverscmp on glibc systems).

> +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);

I found this logic a bit weird, as STRCMP_SORT and VERCMP_SORT are not
mutually exclusive flags, but REVERSE and STRCMP are. I would have
thought REVERSE is the flag, and the other two are selections. Like:

  int flags = 0;

  if (*arg == '-') {
          flags |= REVERSE_SORT;
          arg++;
  }
  if (starts_with(arg, "version:")) {
          *sort = VERCMP_SORT;
          arg += 8;
  } else
          *sort = STRCMP_SORT;

  *sort |= flags;

I think they end up doing the same thing, but maybe I am missing
something.

-Peff

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

[Duy Nguyen]

On Wed, Feb 26, 2014 at 4:05 PM, Jeff King <peff@peff.net> wrote:
> On Tue, Feb 25, 2014 at 07:22:15PM +0700, Nguyễn Thái Ngọc Duy wrote:
>
>> 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.
>
> Cool. I think doing this makes the most sense, as we do not have to
> worry about build-time config (and I do not see any particular reason
> why we would want to use the system strverscmp on glibc systems).

Another reason I want to stay away from glibc is I want to fix the
algorithm to sort YY-preXX and YY-rcXX before YY. There could be
reasons that glibc might reject such a change even if it makes sense
in our context. Even if we make it to newer glibc and fix compat
version, people on older glibc will not receive the fix while people
on compat do. Not so good.

>> +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);
>
> I found this logic a bit weird, as STRCMP_SORT and VERCMP_SORT are not
> mutually exclusive flags, but REVERSE and STRCMP are. I would have
> thought REVERSE is the flag, and the other two are selections. Like:
>
>   int flags = 0;
>
>   if (*arg == '-') {
>           flags |= REVERSE_SORT;
>           arg++;
>   }
>   if (starts_with(arg, "version:")) {
>           *sort = VERCMP_SORT;
>           arg += 8;
>   } else
>           *sort = STRCMP_SORT;
>
>   *sort |= flags;
>
> I think they end up doing the same thing, but maybe I am missing
> something.

No you're not. I did not make it absolute beautiful because I expected
it to be deleted soon after you polish your f-e-r series. Will resend
with this change shortly.
-- 
Duy

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

[Jeff King]

On Wed, Feb 26, 2014 at 06:03:40PM +0700, Duy Nguyen wrote:

> > Cool. I think doing this makes the most sense, as we do not have to
> > worry about build-time config (and I do not see any particular reason
> > why we would want to use the system strverscmp on glibc systems).
> 
> Another reason I want to stay away from glibc is I want to fix the
> algorithm to sort YY-preXX and YY-rcXX before YY. There could be
> reasons that glibc might reject such a change even if it makes sense
> in our context. Even if we make it to newer glibc and fix compat
> version, people on older glibc will not receive the fix while people
> on compat do. Not so good.

Yeah, the handling of -rc has bugged me, too (in my personal alias, I
just grep out the -rc before feeding the list to "sort -V" :) ).

I'd worry slightly, though, that there are other schemes where that
behaves poorly. Should we optimize for git's version numbering, or for
what most other projects want? There could even be room for two types of
version-compare. But before thinking about that, I'd want to know why
glibc behaves as it does.

-Peff

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

[Duy Nguyen]

On Wed, Feb 26, 2014 at 6:08 PM, Jeff King <peff@peff.net> wrote:
> I'd worry slightly, though, that there are other schemes where that
> behaves poorly. Should we optimize for git's version numbering, or for
> what most other projects want? There could even be room for two types of
> version-compare. But before thinking about that, I'd want to know why
> glibc behaves as it does.

We don't have to force one version style for all projects. We could
provide --sort="thisver:refname" vs. "thatver:refname", or put the
"-pre" part in config file. The important thing is we can control the
version algorithm.
-- 
Duy

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

[Jeff King]

On Wed, Feb 26, 2014 at 06:11:54PM +0700, Duy Nguyen wrote:

> On Wed, Feb 26, 2014 at 6:08 PM, Jeff King <peff@peff.net> wrote:
> > I'd worry slightly, though, that there are other schemes where that
> > behaves poorly. Should we optimize for git's version numbering, or for
> > what most other projects want? There could even be room for two types of
> > version-compare. But before thinking about that, I'd want to know why
> > glibc behaves as it does.
> 
> We don't have to force one version style for all projects. We could
> provide --sort="thisver:refname" vs. "thatver:refname", or put the
> "-pre" part in config file. The important thing is we can control the
> version algorithm.

Right, exactly. It may make sense to just do it the way _we_ think is
sensible for now, then, and we can add a glibc-compatible one later if
somebody actually wants it.

-Peff

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

[Duy Nguyen]

On Wed, Feb 26, 2014 at 6:08 PM, Jeff King <peff@peff.net> wrote:
> But before thinking about that, I'd want to know why
> glibc behaves as it does.

Pure guess. It may be because it targets more than software version.
In strverscmp man page, the example is "jan1, jan10, jan2...".
versionsort() in glibc might be the reason that strverscmp was added
and it's used to compare/sort dir entries, so the target might be
numbered log files.
-- 
Duy

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

[Nguyễn Thái Ngọc Duy]

--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>
---
 - add the relicensing note in versioncmp.c
 - reorder the logic in parse_opt_sort for better readability
 - include cache.h instead of git-compat-util.h in versioncmp.c

 Documentation/git-tag.txt |  6 ++++
 Makefile                  |  1 +
 builtin/tag.c             | 71 +++++++++++++++++++++++++++++++++---
 cache.h                   |  2 ++
 t/t7004-tag.sh            | 43 ++++++++++++++++++++++
 versioncmp.c (new)        | 92 +++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 210 insertions(+), 5 deletions(-)
 create mode 100644 versioncmp.c

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..0439c48 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,29 @@ 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;
+	int flags = 0;
+
+	if (*arg == '-') {
+		flags |= REVERSE_SORT;
+		arg++;
+	}
+	if (starts_with(arg, "version:")) {
+		*sort = VERCMP_SORT;
+		arg += 8;
+	} else if (starts_with(arg, "v:")) {
+		*sort = VERCMP_SORT;
+		arg += 2;
+	} else
+		*sort = STRCMP_SORT;
+	if (strcmp(arg, "refname"))
+		die(_("unsupported sort specification %s"), arg);
+	*sort |= flags;
+	return 0;
+}
+
 int cmd_tag(int argc, const char **argv, const char *prefix)
 {
 	struct strbuf buf = STRBUF_INIT;
@@ -437,7 +492,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 +517,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 +568,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..3c876bf
--- /dev/null
+++ b/versioncmp.c
@@ -0,0 +1,92 @@
+#include "cache.h"
+
+/*
+ * versioncmp(): copied from string/strverscmp.c in glibc commit
+ * ee9247c38a8def24a59eb5cfb7196a98bef8cfdc, reformatted to Git coding
+ * style. The implementation is under LGPL-2.1 and Git relicenses it
+ * to GPLv2.
+ */
+
+/*
+ * 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

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

[Jeff King]

On Thu, Feb 27, 2014 at 07:56:52PM +0700, Nguyễn Thái Ngọc Duy wrote:

> --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.

This looks good to me. One minor typo:

> 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

s/tags name/tag names/

You had mentioned earlier tweaking the version comparison to handle
things like -rc better. I think that can come on top of this initial
patch, but we should probably figure out the final sort order before
including this in a release.

-Peff

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

[Duy Nguyen]

On Thu, Feb 27, 2014 at 8:11 PM, Jeff King <peff@peff.net> wrote:
> You had mentioned earlier tweaking the version comparison to handle
> things like -rc better. I think that can come on top of this initial
> patch, but we should probably figure out the final sort order before
> including this in a release.

Yeah I have been thinking about it too. That's why I did not send the
reroll "shortly" as I said. So far I like the idea of using config
file to specify -rc and the like. If XX is in the configured list and
it's the last component in the version string, then reorder it. Seems
to work well with different versioning schemes listed at
http://en.wikipedia.org/wiki/Software_versioning.
-- 
Duy