2.10.0: multiple versionsort.prereleasesuffix buggy?

Hi all

Here's the testing tree https://github.com/woothemes/woocommerce

.git/config has:

[versionsort]

prereleasesuffix = -beta
prereleasesuffix = -RC

$ git tag -l --sort=version:refname
...
2.5.0-RC1
2.5.0-RC2
2.5.0-RC3
2.5.0-beta-1
2.5.0-beta-2
2.5.0-beta-3
2.5.0
2.5.1
2.5.2
2.5.3
2.5.4
2.5.5
2.6.0-RC1
2.6.0-RC2
2.6.0-beta-1
2.6.0-beta-2
2.6.0-beta-3
2.6.0-beta-4
2.6.0
2.6.1
2.6.2
2.6.3
2.6.4

Per documentation, I'm supposed to see something like
...
2.5.0-beta-1
2.5.0-beta-2
2.5.0-beta-3
2.5.0-RC1
2.5.0-RC2
2.5.0-RC3
2.5.0
...

No matter what I do in .git/config, RC goes up front. What's going on?

(Yes, this project's tag capitalization is messed up.)

So that seems wrong. Even weirder, if I set _only_ "-beta", I get:

  $ git tag -l --sort=version:refname | grep -v ^2.6.0
  2.6.0-beta-2
  2.6.0-beta-3
  2.6.0-beta-4
  2.6.0
  2.6.0-RC1
  2.6.0-RC2
  2.6.0-beta-1

Umm...what? beta-1 is sorted away from its companions? That's weird.

I wondered if the presence of "-" after the suffix ("beta-1" rather than "beta1") would matter. It looks like that shouldn't matter, though; it's purely doing a prefix match on "do these names differ at a prerelease suffix".

But something certainly seems wrong.

-Peff

Some of the weirdness is caused by the '-' at the _beginning_ of the suffixes, because versioncmp() gets confused by suffixes starting with the same character(s).

versioncmp() consumes two tagnames up to the first different character and then calls swap_prereleases() to try to match prerelease suffixes starting at those characters. This works fine when comparing a release with a prerelease, e.g. "2.6.0" and "2.6.0-RC1", because swap_prereleases() gets "" and "-RC1" and the latter does match one of the configured suffixes. However, when comparing two prereleases, e.g. "2.6.0-beta1" and "2.6.0-RC1", then the '-' is consumed from both tagnames because the first differing characters are 'b' and 'R', thus swap_prereleases() gets "beta1" and "RC1", which, of course, don't match any of the configured suffixes without the leading '-'.

It's way past my bedtime, so for the time being I can only come up with a hacky configuration workaround that seems to deliver the expected results:

[versionsort]
prereleasesuffix = beta
prereleasesuffix = -beta
prereleasesuffix = RC
prereleasesuffix = -RC

Best,
Gábor

Oh, right, that makes sense. So it's effectively not finding _any_ suffix between X-RC1 and X-beta-1, because we only start looking after "X-", and none of them match.

I am still confused why "2.6.0-beta-1" doesn't get sorted with its peers. I'd guess that the comparison function doesn't actually provide a strict ordering, so the results depend on the actual sort algorithm, and which pairs it ends up comparing.

-Peff

Hi,

Quoting Jeff King <[email protected]>:

Turns out that this weirdness is caused by that leading '-' in the suffix, too.

Here is a manageably small recipe to reproduce:

    $ git -c versionsort.prereleasesuffix=-beta tag -l  
--sort=version:refname v2.1.0* v2.1.{1,2}
    v2.1.0-beta-2
    v2.1.0-beta-3
    v2.1.0
    v2.1.0-RC1
    v2.1.0-RC2
    v2.1.0-beta-1
    v2.1.1
    v2.1.2

Tracing which pairs of tagnames are compared, I found that somewhere along the line "v2.1.0-beta-1" happens to be compared to "v2.1.0-RC2", and the issue described in my previous email strikes again: the '-' is part of the common part of the two tagnames, swap_prereleases() gets only "beta-1" and "RC2", thus it can't match the configured "-beta" suffix, and since the byte value of 'b' is higher than that of 'R', "-beta-1" is sorted after "-RC2". OTOH, "v2.1.0-beta-2" and "v2.1.0-beta-3" are only compared to each other or to final release tags, but never to any "-RCx" tags, hence they are sorted properly.

Once I finish teaching versioncmp() and swap_prereleases() to cope with leading characters of a prereleaseSuffix being part of the common part of two tagnames, this out-of-order "beta-1" issue will be gone as well.

Best,
Gábor

(Sorry for double post, forgot to Cc: the mailing list...)

This series fixes a bug, where version sort with prerelease reordering puts tagnames in the wrong order, when the common part of two compared tagnames ends with the leading character(s) of one or more configured prerelease suffixes. More details in the final patch.

The first two patches are test cleanups, the first is an independent "while at it", but the second one touches tests that are modified by later patches of this series. The rest is rather straightforward: add failing tests, do some refactoring, and finally fix the bug.

SZEDER Gábor (5):
t7004-tag: delete unnecessary tags with test_when_finished
t7004-tag: use test_config helper
t7004-tag: add version sort tests to show prerelease reordering issues
versioncmp: pass full tagnames to swap_prereleases()
versioncmp: cope with common leading parts in
versionsort.prereleaseSuffix

 t/t7004-tag.sh | 83 ++++++++++++++++++++++++++++++++++++++++------------------
 versioncmp.c   | 46 +++++++++++++++++++++-----------
 2 files changed, 87 insertions(+), 42 deletions(-)

2.10.0.74.g6632b1b

The '--force is moot with a non-existing tag name' test creates two new tags, which are then deleted right after the test is finished, outside the test_expect_success block, allowing 'git tag -d's output to pollute the test output.

Use test_when_finished to delete those tags.

---
 t/t7004-tag.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 8b0f71a2ac15..396cffeeb5ad 100755
@@ -122,11 +122,11 @@ test_expect_success '--force can create a tag with the name of one existing' '
 	tag_exists mytag'
 
 test_expect_success '--force is moot with a non-existing tag name' '
+	test_when_finished git tag -d newtag forcetag &&
 	git tag newtag >expect &&
 	git tag --force forcetag >actual &&
 	test_cmp expect actual
 '
-git tag -d newtag forcetag
 
 # deleting tags:
 

2.10.0.74.g6632b1b

... instead of setting and then manually unsetting configuration variables, on one occasion even outside the test_expect_success block.

---
 t/t7004-tag.sh | 23 ++++++++++-------------
 1 file changed, 10 insertions(+), 13 deletions(-)

index 396cffeeb5ad..920a1b4b2e58 100755
@@ -297,11 +297,9 @@ EOF
 '
 
 test_expect_success 'listing tags in column with column.*' '
-	git config column.tag row &&
-	git config column.ui dense &&
+	test_config column.tag row &&
+	test_config column.ui dense &&
 	COLUMNS=40 git tag -l >actual &&
-	git config --unset column.ui &&
-	git config --unset column.tag &&
 	cat >expected <<\EOF &&
 a1      aa1   cba     t210    t211
 v0.2.1  v1.0  v1.0.1  v1.1.3

@@ -314,9 +312,8 @@ test_expect_success 'listing tag with -n --column should fail' '
 '
 
 test_expect_success 'listing tags -n in column with column.ui ignored' '
-	git config column.ui "row dense" &&
+	test_config column.ui "row dense" &&
 	COLUMNS=40 git tag -l -n >actual &&
-	git config --unset column.ui &&
 	cat >expected <<\EOF &&
 a1              Foo
 aa1             Foo

@@ -1200,11 +1197,10 @@ test_expect_success GPG,RFC1991 \
 '
 
 # try to sign with bad user.signingkey
-git config user.signingkey BobTheMouse
 test_expect_success GPG \
 	'git tag -s fails if gpg is misconfigured (bad key)' \
-	'test_must_fail git tag -s -m tail tag-gpg-failure'
-git config --unset user.signingkey
+	'test_config user.signingkey BobTheMouse &&
+	test_must_fail git tag -s -m tail tag-gpg-failure'
 
 # try to produce invalid signature
 test_expect_success GPG \

@@ -1484,7 +1480,7 @@ test_expect_success 'reverse lexical sort' '
 '
 
 test_expect_success 'configured lexical sort' '
-	git config tag.sort "v:refname" &&
+	test_config tag.sort "v:refname" &&
 	git tag -l "foo*" >actual &&
 	cat >expect <<-\EOF &&
 	foo1.3

@@ -1495,6 +1491,7 @@ test_expect_success 'configured lexical sort' '
 '
 
 test_expect_success 'option override configured sort' '
+	test_config tag.sort "v:refname" &&
 	git tag -l --sort=-refname "foo*" >actual &&
 	cat >expect <<-\EOF &&
 	foo1.6

@@ -1509,13 +1506,12 @@ test_expect_success 'invalid sort parameter on command line' '
 '
 
 test_expect_success 'invalid sort parameter in configuratoin' '
-	git config tag.sort "v:notvalid" &&
+	test_config tag.sort "v:notvalid" &&
 	test_must_fail git tag -l "foo*"
 '
 
 test_expect_success 'version sort with prerelease reordering' '
-	git config --unset tag.sort &&
-	git config versionsort.prereleaseSuffix -rc &&
+	test_config versionsort.prereleaseSuffix -rc &&
 	git tag foo1.6-rc1 &&
 	git tag foo1.6-rc2 &&
 	git tag -l --sort=version:refname "foo*" >actual &&

@@ -1530,6 +1526,7 @@ test_expect_success 'version sort with prerelease reordering' '
 '
 
 test_expect_success 'reverse version sort with prerelease reordering' '
+	test_config versionsort.prereleaseSuffix -rc &&
 	git tag -l --sort=-version:refname "foo*" >actual &&
 	cat >expect <<-\EOF &&
 	foo1.10

2.10.0.74.g6632b1b

Version sort with prerelease reordering sometimes puts tagnames in the wrong order, when the common part of two compared tagnames ends with the leading character(s) of one or more configured prerelease suffixes. Add tests that demonstrate these issues.

The unrelated '--format should list tags as per format given' test later uses tags matching the same prefix as the version sort tests, thus was affected by the new tags added for the new tests in this patch. Change that test to perform its checks on a different set of tags.

---
 t/t7004-tag.sh | 62 +++++++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 48 insertions(+), 14 deletions(-)

index 920a1b4b2e58..d69ac4940388 100755
@@ -1511,14 +1511,14 @@ test_expect_success 'invalid sort parameter in configuratoin' '
 '
 
 test_expect_success 'version sort with prerelease reordering' '
-	test_config versionsort.prereleaseSuffix -rc &&
-	git tag foo1.6-rc1 &&
-	git tag foo1.6-rc2 &&
+	test_config versionsort.prereleaseSuffix -beta &&
+	git tag foo1.6-beta1 &&
+	git tag foo1.6-beta2 &&
 	git tag -l --sort=version:refname "foo*" >actual &&
 	cat >expect <<-\EOF &&
 	foo1.3
-	foo1.6-rc1
-	foo1.6-rc2
+	foo1.6-beta1
+	foo1.6-beta2
 	foo1.6
 	foo1.10
 	EOF

@@ -1526,18 +1526,54 @@ test_expect_success 'version sort with prerelease reordering' '
 '
 
 test_expect_success 'reverse version sort with prerelease reordering' '
-	test_config versionsort.prereleaseSuffix -rc &&
+	test_config versionsort.prereleaseSuffix -beta &&
 	git tag -l --sort=-version:refname "foo*" >actual &&
 	cat >expect <<-\EOF &&
 	foo1.10
 	foo1.6
-	foo1.6-rc2
-	foo1.6-rc1
+	foo1.6-beta2
+	foo1.6-beta1
 	foo1.3
 	EOF
 	test_cmp expect actual
 '
 
+test_expect_failure 'version sort with prerelease reordering and common leading character' '
+	test_config versionsort.prereleaseSuffix -beta &&
+	git tag foo1.6-after1 &&
+	git tag -l --sort=version:refname "foo*" >actual &&
+	cat >expect <<-\EOF &&
+	foo1.3
+	foo1.6-beta1
+	foo1.6-beta2
+	foo1.6
+	foo1.6-after1
+	foo1.10
+	EOF
+	test_cmp expect actual
+'
+
+# Capitalization of suffixes is important here, because "-RC" would normally
+# be sorted before "-beta" and the config settings should override that.
+test_expect_failure 'version sort with prerelease reordering, multiple suffixes and common leading character' '
+	test_config versionsort.prereleaseSuffix -beta &&
+	git config --add versionsort.prereleaseSuffix -RC &&
+	git tag foo1.6-RC1 &&
+	git tag foo1.6-RC2 &&
+	git tag -l --sort=version:refname "foo*" >actual &&
+	cat >expect <<-\EOF &&
+	foo1.3
+	foo1.6-beta1
+	foo1.6-beta2
+	foo1.6-RC1
+	foo1.6-RC2
+	foo1.6
+	foo1.6-after1
+	foo1.10
+	EOF
+	test_cmp expect actual
+'
+
 run_with_limited_stack () {
 	(ulimit -s 128 && "$@")
 }

@@ -1566,13 +1602,11 @@ EOF"
 
 test_expect_success '--format should list tags as per format given' '
 	cat >expect <<-\EOF &&
-	refname : refs/tags/foo1.10
-	refname : refs/tags/foo1.3
-	refname : refs/tags/foo1.6
-	refname : refs/tags/foo1.6-rc1
-	refname : refs/tags/foo1.6-rc2
+	refname : refs/tags/v1.0
+	refname : refs/tags/v1.0.1
+	refname : refs/tags/v1.1.3
 	EOF
-	git tag -l --format="refname : %(refname)" "foo*" >actual &&
+	git tag -l --format="refname : %(refname)" "v1*" >actual &&
 	test_cmp expect actual
 '
 

2.10.0.74.g6632b1b

The swap_prereleases() helper function is responsible for finding configured prerelease suffixes in a pair of tagnames to be compared, but this function currently only gets to see only the parts of those two tagnames starting at the first different character. To fix some issues related to multiple prerelease suffixes starting with the same leading character(s), this helper function must see the preceeding matching characters as well.

In preparation for the fix in the following patch, refactor swap_prereleases() and its caller to pass two full tagnames and an additional offset indicating the position of the first different character.

---
 versioncmp.c | 28 ++++++++++++++--------------
 1 file changed, 14 insertions(+), 14 deletions(-)

index 80bfd109fa12..fed02d2a2878 100644
@@ -25,32 +25,31 @@ static const struct string_list *prereleases;
 static int initialized;
 
 /*
- * p1 and p2 point to the first different character in two strings. If
- * either p1 or p2 starts with a prerelease suffix, it will be forced
- * to be on top.
+ * off is the offset of the first different character in the two strings
+ * s1 and s2. If either s1 or s2 contains a prerelease suffix starting
+ * at that offset, it will be forced to be on top.
  *
- * If both p1 and p2 start with (different) suffix, the order is
- * determined by config file.
+ * If both s1 and s2 contain a (different) suffix at that position, the
+ * order is determined by config file.
  *
- * Note that we don't have to deal with the situation when both p1 and
- * p2 start with the same suffix because the common part is already
+ * Note that we don't have to deal with the situation when both s1 and
+ * s2 contain the same suffix because the common part is already
  * consumed by the caller.
  *
  * Return non-zero if *diff contains the return value for versioncmp()
  */
-static int swap_prereleases(const void *p1_,
-			    const void *p2_,
+static int swap_prereleases(const char *s1,
+			    const char *s2,
+			    int off,
 			    int *diff)
 {
-	const char *p1 = p1_;
-	const char *p2 = p2_;
 	int i, i1 = -1, i2 = -1;
 
 	for (i = 0; i < prereleases->nr; i++) {
 		const char *suffix = prereleases->items[i].string;
-		if (i1 == -1 && starts_with(p1, suffix))
+		if (i1 == -1 && starts_with(s1 + off, suffix))
 			i1 = i;
-		if (i2 == -1 && starts_with(p2, suffix))
+		if (i2 == -1 && starts_with(s2 + off, suffix))
 			i2 = i;
 	}
 	if (i1 == -1 && i2 == -1)

@@ -121,7 +120,8 @@ int versioncmp(const char *s1, const char *s2)
 		initialized = 1;
 		prereleases = git_config_get_value_multi("versionsort.prereleasesuffix");
 	}
-	if (prereleases && swap_prereleases(p1 - 1, p2 - 1, &diff))
+	if (prereleases && swap_prereleases(s1, s2, (const char *) p1 - s1 - 1,
+					    &diff))
 		return diff;
 
 	state = result_type[state * 3 + (((c2 == '0') + (isdigit (c2) != 0)))];

2.10.0.74.g6632b1b

"The common part is already consumed" was relevant while the function was fed p1 and p2, i.e. the first difference, but the whole point of passing the original s1 and s2 with ofs is so that the function can look behind ofs as necessary. Is "already consumed" still correct (or relevant) with s/p/s/ you did to its calling convention?

Quoting Junio C Hamano <[email protected]>:

Well, it's still correct in the sense that we don't have to worry about finding the same suffix in both strings. However, "consume" is not the right word to use here, as incrementing an offset until it points past the common part doesn't count as "consumption", so more rewording would be necessary.

I'm not sure about the relevancy of this pararaph, or the relevancy of the original version for that matter. I mean, there is a different character for sure, so it's really rather obvious that it can't possibly be the same suffix in both, isn't it? So I don't think it adds much value, and don't mind deleting it in the reroll.

Best,
Gábor

Concurred. Let's lose this confusing statement.

Thanks.

Version sort with prerelease reordering sometimes puts tagnames in the wrong order, when the common part of two compared tagnames ends with the leading character(s) of one or more configured prerelease suffixes.

  $ git config --get-all versionsort.prereleaseSuffix
  -beta
  $ git tag -l --sort=version:refname v2.1.*
  v2.1.0-beta-2
  v2.1.0-beta-3
  v2.1.0
  v2.1.0-RC1
  v2.1.0-RC2
  v2.1.0-beta-1
  v2.1.1
  v2.1.2

The reason is that when comparing a pair of tagnames, first versioncmp() looks for the first different character in a pair of tagnames, and then the swap_prereleases() helper function checks for prerelease suffixes _starting at_ that character. Thus, when in the above example the sorting algorithm happens to compare the tagnames "v2.1.0-beta-1" and "v2.1.0-RC2", swap_prereleases() will try to match the suffix "-beta" against "beta-1" to no avail, and the two tagnames erroneously end up being ordered lexicographically.

To fix this issue change swap_prereleases() to look for configured prerelease suffixes containing that first different character.

---
 t/t7004-tag.sh |  4 ++--
 versioncmp.c   | 24 +++++++++++++++++++-----
 2 files changed, 21 insertions(+), 7 deletions(-)

index d69ac4940388..f0cfe1fa3d8b 100755
@@ -1538,7 +1538,7 @@ test_expect_success 'reverse version sort with prerelease reordering' '
 	test_cmp expect actual
 '
 
-test_expect_failure 'version sort with prerelease reordering and common leading character' '
+test_expect_success 'version sort with prerelease reordering and common leading character' '
 	test_config versionsort.prereleaseSuffix -beta &&
 	git tag foo1.6-after1 &&
 	git tag -l --sort=version:refname "foo*" >actual &&

@@ -1555,7 +1555,7 @@ test_expect_failure 'version sort with prerelease reordering and common leading
 
 # Capitalization of suffixes is important here, because "-RC" would normally
 # be sorted before "-beta" and the config settings should override that.
-test_expect_failure 'version sort with prerelease reordering, multiple suffixes and common leading character' '
+test_expect_success 'version sort with prerelease reordering, multiple suffixes and common leading character' '
 	test_config versionsort.prereleaseSuffix -beta &&
 	git config --add versionsort.prereleaseSuffix -RC &&
 	git tag foo1.6-RC1 &&

index fed02d2a2878..87b49a622423 100644
@@ -27,7 +27,8 @@ static int initialized;
 /*
  * off is the offset of the first different character in the two strings
  * s1 and s2. If either s1 or s2 contains a prerelease suffix starting
- * at that offset, it will be forced to be on top.
+ * at that offset or the character at that offset is part of a
+ * prerelease suffix, then that string will be forced to be on top.
  *
  * If both s1 and s2 contain a (different) suffix at that position, the
  * order is determined by config file.

@@ -47,10 +48,23 @@ static int swap_prereleases(const char *s1,
 
 	for (i = 0; i < prereleases->nr; i++) {
 		const char *suffix = prereleases->items[i].string;
-		if (i1 == -1 && starts_with(s1 + off, suffix))
-			i1 = i;
-		if (i2 == -1 && starts_with(s2 + off, suffix))
-			i2 = i;
+		int j, start, suffix_len = strlen(suffix);
+		if (suffix_len < off)
+			start = off - suffix_len + 1;
+		else
+			start = 0;
+		for (j = start; j <= off; j++) {
+			if (i1 == -1 && starts_with(s1 + j, suffix)) {
+				i1 = i;
+				break;
+			}
+		}
+		for (j = start; j <= off; j++) {
+			if (i2 == -1 && starts_with(s2 + j, suffix)) {
+				i2 = i;
+				break;
+			}
+		}
 	}
 	if (i1 == -1 && i2 == -1)
 		return 0;

2.10.0.74.g6632b1b

Quoting SZEDER Gábor <[email protected]>:

Now, while I believe this is the right thing to do to fix this bug, there is a corner case, where multiple configured prerelease suffixes might match the same tagname:

  $ git config --get-all versionsort.prereleaseSuffix
  -bar
  -baz
  -foo-bar
  $ ~/src/git/git tag -l --sort=version:refname
  v1.0-foo-bar
  v1.0-foo-baz

I.e. when comparing these two tags, both "-bar" and "-foo-bar" would match "v1.0-foo-bar", and as "-bar" comes first in the config file, it wins, and "v1.0-foo-bar" is ordered first. An argument could be made to prefer longer matches, in which case "v1.0-foo-bar" would be ordered according to "-foo-bar", i.e. as second. However, I don't know what that argument could be, to me neither behavior is better than the other, but the implementation of the "longest match counts" would certainly be more complicated.

The argument I would make is that this is a pathological corner case that doesn't worth worrying about.

Best,
Gábor

Maybe we should keep a note about this in config.txt? If it's not worth bothering/scaring the users about, I suggest you keep this in the commit message.

Duy

Quoting SZEDER Gábor <[email protected]>:

After having slept on this a couple of times, I think the longest matching prerelease suffix should determine the sorting order.

A release tag usually consists of an optional prefix, e.g. 'v' or 'snapshot-', followed by the actual version number, followed by an optional suffix. In the contrived example quoted above this suffix is '-foo-bar', thus it feels wrong to match '-bar' against it, when the user explicitly configured '-foo-bar' as prerelease suffix as well.

Then here is a more realistic case for sorting based on the longest matching suffix, where

- a longer suffix starts with the shorter one,
- and the longer suffix comes after the shorter one in the configuration.

With my patches it looks like this:

   $ git -c versionsort.prereleasesuffix=-pre \
         -c versionsort.prereleasesuffix=-prerelease \
         tag -l --sort=version:refname
   v1.0.0-prerelease1
   v1.0.0-pre1
   v1.0.0-pre2
   v1.0.0

Yeah, having both '-pre' and '-prerelease' suffixes seems somewhat silly, but who knows what similar but more reasonable prerelease suffixes e.g. non-English speaking users might use in their native language.

Anyway, my intuition says that any '-prereleaseX' tags should come after all the '-preX' tags. (Ironically, current git just happens to get this particular case right.)

My patches get this wrong, because they look for prerelease suffixes _containing_ the first different character. However, when a '-preX' and a '-prereleaseX' tag are compared, then the whole '-pre' suffix is part of the common part, thus it doesn't match, only '-prerelease' matches.

So, to sort this case right the implementation should

- look for a prerelease suffix containing the first different character or ending right before the first different character, (This means that when comparing 'v1.0.0-pre1' and 'v1.0.0-pre2' swap_prereleases() would match '-pre' in both: no big deal, it should return "undecided" and let the caller do the right thing by sorting based on '1' and '2')

- and sort a tag based on the longest matching prerelease suffix. (In my quoted email above I alluded that its implementation must be more complicated. No, it turns out that it actually isn't.)

(Just for the record: it's still not 100% foolproof, though. Someone asking for trouble might use letters instead of numbers to indicate subsequent prereleases, and might have tags 'v1.0-prea', 'v1.0-preb', ..., 'v1.0-prer', and 'v1.0-prerelease'. In this case the sorting algorithm might happen to decide to compare 'v1.0-prer' and 'v1.0-prerelease', and since the common part is 'v1.0-prer' it will fail to recognize the '-pre' suffix. I don't see how this case could be supported in a sane way, or why it's worth to support it.)

And a final sidenote: sorting based on the longest matching suffix also allows us to (ab)use version sort with prerelease suffixes to sort postrelease tags as we please, too:

  $ ~/src/git/git -c versionsort.prereleasesuffix=-alpha \
                  -c versionsort.prereleasesuffix=-beta \
                  -c versionsort.prereleasesuffix= \
                  -c versionsort.prereleasesuffix=-gamma \
                  -c versionsort.prereleasesuffix=-delta \
                  tag -l --sort=version:refname 'v3.0*'
  v3.0-alpha1
  v3.0-beta1
  v3.0
  v3.0-gamma1
  v3.0-delta1

So, unless I hear a counterargument, I will submit a reroll with longest matching suffix determining sort order added on top once I get around to finish up its commit message.

Best,
Gábor

Assuming that gamma and delta are meant to indicate "these are post-release updates", I think a mechanism that can yield the above result is fantastic ;-)

Quoting Junio C Hamano <[email protected]>:

Indeed they were meant as post-release suffixes. Naturally following alpha and beta, they were the first to spring to mind that should be sorted in non-lexicographical order, so I could show of postrelease reordering. It's just that we don't have a config like 'versionsort.postreleasesuffix', which is half the abuse. The other half of the abuse is that I had to explicitly indicate the position of suffixless versions with an empty suffix between pre- and postrelease suffixes. The empty suffix matches on every tag, but then it's overridden by all configured suffixes, so such a version just stays in the middle.

Heh.

Gut feeling tells me that I should take this as a subtle encouragement to look into adding 'versionsort.postreleasesuffix', shouldn't I ;)

It is more like "this made me realize that these are merely 'suffix' after the real release name, no pre- or post- about them", also known as "I think PREreleasesuffix was a mistake and we weren't thinking clearly enough when we added it."

To me, this looks like a list of possible suffixes that can include an empty suffix to denote "the real thing", e.g.

    versionsort.suffix = "-alpha" "-beta" "" "-gamma" "-delta"

and that position in the list determines the order of things inside the same family of versions that share the same "non-suffix" part.

This is what makes sense to me. Perhaps migrade to "releasesuffix" and deprecate "prereleasesuffix"? I don't think that's too painful especially if git accepts the old value and warns about it's deprecation? That or we can just stick with calling it pre-release and they sort based on order with '' being the empty value?

Thanks,
Jake

Even though this is mostly used with tag listing, it can be used with branch listing and general refs as well, where "release" does not really make sense. So I prefer the name versionsort.suffix to versionsort.releasesuffix.

Yeah deprecation is good, we don't want to support to config keys with different algorithms forever.

Duy

After having slept on it a few (erm...) more times...

At the risk of overthinking it: I think it would be more correct to say that the earliest starting matching prerelease suffix should determine the sorting order in the first place.

And when there happen to be more than one matching suffixes starting at the same earliest position, then we should pick the longest of them. The new patch 6/7 implements this behavior.

Changes since v1:
- Documentation, in-code comment and commit message updates.
- Use different tagnames and suffixes in the tests, keeping the new tests simpler and changes to existing tests smaller.
- Added a test of questionable value to try to check that we don't read memory before the tagname strings in case of an unusually long suffix.
- Removed unnecessary {}.
- Added two patches on top to address the corner cases and to introduce 'versionsort.suffix' for the resulting more general suffix reordering behavior.

The interdiff at the bottom is between v1 and only the first five patches of v2, i.e. not including the two new patches. I think it's easier to judge the changes this way.

SZEDER Gábor (7):
t7004-tag: delete unnecessary tags with test_when_finished
t7004-tag: use test_config helper
t7004-tag: add version sort tests to show prerelease reordering issues
versioncmp: pass full tagnames to swap_prereleases()
versioncmp: cope with common part overlapping with prerelease suffix
versioncmp: use earliest-longest contained suffix to determine sorting
order
versioncmp: generalize version sort suffix reordering

 Documentation/config.txt  |  44 ++++++++++++----
 Documentation/git-tag.txt |   4 +-
 t/t7004-tag.sh            | 132 +++++++++++++++++++++++++++++++++++++++-------
 versioncmp.c              |  68 +++++++++++++++++-------
 4 files changed, 196 insertions(+), 52 deletions(-)

2.11.0.78.g5a2d011

index 0bcb6790d..c1a9616e9 100644
@@ -3008,8 +3008,12 @@ versionsort.prereleaseSuffix::
 This variable can be specified multiple times, once per suffix. The
 order of suffixes in the config file determines the sorting order
 (e.g. if "-pre" appears before "-rc" in the config file then 1.0-preXX
-is sorted before 1.0-rcXX). The sorting order between different
-suffixes is undefined if they are in multiple config files.
+is sorted before 1.0-rcXX).
+If more than one suffixes match the same tagname, then that tagname will
+be sorted according to the matching suffix which comes first in the
+configuration.
+The sorting order between different suffixes is undefined if they are
+in multiple config files.
 
 web.browser::
 	Specify a web browser that may be used by some commands.

index 87b49a622..f86ac562e 100644
@@ -26,16 +26,15 @@ static int initialized;
 
 /*
  * off is the offset of the first different character in the two strings
- * s1 and s2. If either s1 or s2 contains a prerelease suffix starting
- * at that offset or the character at that offset is part of a
- * prerelease suffix, then that string will be forced to be on top.
+ * s1 and s2. If either s1 or s2 contains a prerelease suffix containing
+ * that offset, then that string will be forced to be on top.
  *
- * If both s1 and s2 contain a (different) suffix at that position, the
- * order is determined by config file.
- *
- * Note that we don't have to deal with the situation when both s1 and
- * s2 contain the same suffix because the common part is already
- * consumed by the caller.
+ * If both s1 and s2 contain a (different) suffix around that position,
+ * their order is determined by the order of those two suffixes in the
+ * configuration.
+ * If any of the strings contains more than one different suffixes around
+ * that position, then that string is sorted according to the contained
+ * suffix which comes first in the configuration.
  *
  * Return non-zero if *diff contains the return value for versioncmp()
  */

@@ -53,18 +52,16 @@ static int swap_prereleases(const char *s1,
 			start = off - suffix_len + 1;
 		else
 			start = 0;
-		for (j = start; j <= off; j++) {
+		for (j = start; j <= off; j++)
 			if (i1 == -1 && starts_with(s1 + j, suffix)) {
 				i1 = i;
 				break;
 			}
-		}
-		for (j = start; j <= off; j++) {
+		for (j = start; j <= off; j++)
 			if (i2 == -1 && starts_with(s2 + j, suffix)) {
 				i2 = i;
 				break;
 			}
-		}
 	}
 	if (i1 == -1 && i2 == -1)
 		return 0;

The '--force is moot with a non-existing tag name' test creates two new tags, which are then deleted right after the test is finished, outside the test_expect_success block, allowing 'git tag -d's output to pollute the test output.

Use test_when_finished to delete those tags.

---
 t/t7004-tag.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 8b0f71a2a..396cffeeb 100755
@@ -122,11 +122,11 @@ test_expect_success '--force can create a tag with the name of one existing' '
 	tag_exists mytag'
 
 test_expect_success '--force is moot with a non-existing tag name' '
+	test_when_finished git tag -d newtag forcetag &&
 	git tag newtag >expect &&
 	git tag --force forcetag >actual &&
 	test_cmp expect actual
 '
-git tag -d newtag forcetag
 
 # deleting tags:
 

2.11.0.78.g5a2d011

... instead of setting and then manually unsetting configuration variables, on one occasion even outside the test_expect_success block.

---
 t/t7004-tag.sh | 23 ++++++++++-------------
 1 file changed, 10 insertions(+), 13 deletions(-)

index 396cffeeb..920a1b4b2 100755
@@ -297,11 +297,9 @@ EOF
 '
 
 test_expect_success 'listing tags in column with column.*' '
-	git config column.tag row &&
-	git config column.ui dense &&
+	test_config column.tag row &&
+	test_config column.ui dense &&
 	COLUMNS=40 git tag -l >actual &&
-	git config --unset column.ui &&
-	git config --unset column.tag &&
 	cat >expected <<\EOF &&
 a1      aa1   cba     t210    t211
 v0.2.1  v1.0  v1.0.1  v1.1.3

@@ -314,9 +312,8 @@ test_expect_success 'listing tag with -n --column should fail' '
 '
 
 test_expect_success 'listing tags -n in column with column.ui ignored' '
-	git config column.ui "row dense" &&
+	test_config column.ui "row dense" &&
 	COLUMNS=40 git tag -l -n >actual &&
-	git config --unset column.ui &&
 	cat >expected <<\EOF &&
 a1              Foo
 aa1             Foo

@@ -1200,11 +1197,10 @@ test_expect_success GPG,RFC1991 \
 '
 
 # try to sign with bad user.signingkey
-git config user.signingkey BobTheMouse
 test_expect_success GPG \
 	'git tag -s fails if gpg is misconfigured (bad key)' \
-	'test_must_fail git tag -s -m tail tag-gpg-failure'
-git config --unset user.signingkey
+	'test_config user.signingkey BobTheMouse &&
+	test_must_fail git tag -s -m tail tag-gpg-failure'
 
 # try to produce invalid signature
 test_expect_success GPG \

@@ -1484,7 +1480,7 @@ test_expect_success 'reverse lexical sort' '
 '
 
 test_expect_success 'configured lexical sort' '
-	git config tag.sort "v:refname" &&
+	test_config tag.sort "v:refname" &&
 	git tag -l "foo*" >actual &&
 	cat >expect <<-\EOF &&
 	foo1.3

@@ -1495,6 +1491,7 @@ test_expect_success 'configured lexical sort' '
 '
 
 test_expect_success 'option override configured sort' '
+	test_config tag.sort "v:refname" &&
 	git tag -l --sort=-refname "foo*" >actual &&
 	cat >expect <<-\EOF &&
 	foo1.6

@@ -1509,13 +1506,12 @@ test_expect_success 'invalid sort parameter on command line' '
 '
 
 test_expect_success 'invalid sort parameter in configuratoin' '
-	git config tag.sort "v:notvalid" &&
+	test_config tag.sort "v:notvalid" &&
 	test_must_fail git tag -l "foo*"
 '
 
 test_expect_success 'version sort with prerelease reordering' '
-	git config --unset tag.sort &&
-	git config versionsort.prereleaseSuffix -rc &&
+	test_config versionsort.prereleaseSuffix -rc &&
 	git tag foo1.6-rc1 &&
 	git tag foo1.6-rc2 &&
 	git tag -l --sort=version:refname "foo*" >actual &&

@@ -1530,6 +1526,7 @@ test_expect_success 'version sort with prerelease reordering' '
 '
 
 test_expect_success 'reverse version sort with prerelease reordering' '
+	test_config versionsort.prereleaseSuffix -rc &&
 	git tag -l --sort=-version:refname "foo*" >actual &&
 	cat >expect <<-\EOF &&
 	foo1.10

2.11.0.78.g5a2d011

Version sort with prerelease reordering sometimes puts tagnames in the wrong order, when the common part of two compared tagnames ends with the leading character(s) of one or more configured prerelease suffixes. Add tests that demonstrate these issues.

The unrelated '--format should list tags as per format given' test later uses tags matching the same prefix as the version sort tests, thus was affected by the new tags added for the new tests in this patch. Change that test to perform its checks on a different set of tags.

---
 t/t7004-tag.sh | 36 ++++++++++++++++++++++++++++++------
 1 file changed, 30 insertions(+), 6 deletions(-)

index 920a1b4b2..6445aae29 100755
@@ -1538,6 +1538,32 @@ test_expect_success 'reverse version sort with prerelease reordering' '
 	test_cmp expect actual
 '
 
+test_expect_failure 'version sort with prerelease reordering and common leading character' '
+	test_config versionsort.prereleaseSuffix -before &&
+	git tag foo1.7-before1 &&
+	git tag foo1.7 &&
+	git tag foo1.7-after1 &&
+	git tag -l --sort=version:refname "foo1.7*" >actual &&
+	cat >expect <<-\EOF &&
+	foo1.7-before1
+	foo1.7
+	foo1.7-after1
+	EOF
+	test_cmp expect actual
+'
+
+test_expect_failure 'version sort with prerelease reordering, multiple suffixes and common leading character' '
+	test_config versionsort.prereleaseSuffix -before &&
+	git config --add versionsort.prereleaseSuffix -after &&
+	git tag -l --sort=version:refname "foo1.7*" >actual &&
+	cat >expect <<-\EOF &&
+	foo1.7-before1
+	foo1.7-after1
+	foo1.7
+	EOF
+	test_cmp expect actual
+'
+
 run_with_limited_stack () {
 	(ulimit -s 128 && "$@")
 }

@@ -1566,13 +1592,11 @@ EOF"
 
 test_expect_success '--format should list tags as per format given' '
 	cat >expect <<-\EOF &&
-	refname : refs/tags/foo1.10
-	refname : refs/tags/foo1.3
-	refname : refs/tags/foo1.6
-	refname : refs/tags/foo1.6-rc1
-	refname : refs/tags/foo1.6-rc2
+	refname : refs/tags/v1.0
+	refname : refs/tags/v1.0.1
+	refname : refs/tags/v1.1.3
 	EOF
-	git tag -l --format="refname : %(refname)" "foo*" >actual &&
+	git tag -l --format="refname : %(refname)" "v1*" >actual &&
 	test_cmp expect actual
 '
 

2.11.0.78.g5a2d011

The swap_prereleases() helper function is responsible for finding configured prerelease suffixes in a pair of tagnames to be compared, but this function currently gets to see only the parts of those two tagnames starting at the first different character. To fix some issues related to the common part of two tagnames overlapping with leading part of a prerelease suffix, this helper function must see both full tagnames.

In preparation for the fix in the following patch, refactor swap_prereleases() and its caller to pass two full tagnames and an additional offset indicating the position of the first different character.

While updating the comment describing that function, remove the sentence about not dealing with both tagnames having the same suffix. Currently it doesn't add much value (we know that there is a different character, so it's obvious that it can't possibly be the same suffix in both), and at the end of this patch series it won't even be true anymore.

---
 versioncmp.c | 29 +++++++++++++----------------
 1 file changed, 13 insertions(+), 16 deletions(-)

index 80bfd109f..a55c23ad5 100644
@@ -25,32 +25,28 @@ static const struct string_list *prereleases;
 static int initialized;
 
 /*
- * p1 and p2 point to the first different character in two strings. If
- * either p1 or p2 starts with a prerelease suffix, it will be forced
- * to be on top.
+ * off is the offset of the first different character in the two strings
+ * s1 and s2. If either s1 or s2 contains a prerelease suffix starting
+ * at that offset, it will be forced to be on top.
  *
- * If both p1 and p2 start with (different) suffix, the order is
- * determined by config file.
- *
- * Note that we don't have to deal with the situation when both p1 and
- * p2 start with the same suffix because the common part is already
- * consumed by the caller.
+ * If both s1 and s2 contain a (different) suffix at that position,
+ * their order is determined by the order of those two suffixes in the
+ * configuration.
  *
  * Return non-zero if *diff contains the return value for versioncmp()
  */
-static int swap_prereleases(const void *p1_,
-			    const void *p2_,
+static int swap_prereleases(const char *s1,
+			    const char *s2,
+			    int off,
 			    int *diff)
 {
-	const char *p1 = p1_;
-	const char *p2 = p2_;
 	int i, i1 = -1, i2 = -1;
 
 	for (i = 0; i < prereleases->nr; i++) {
 		const char *suffix = prereleases->items[i].string;
-		if (i1 == -1 && starts_with(p1, suffix))
+		if (i1 == -1 && starts_with(s1 + off, suffix))
 			i1 = i;
-		if (i2 == -1 && starts_with(p2, suffix))
+		if (i2 == -1 && starts_with(s2 + off, suffix))
 			i2 = i;
 	}
 	if (i1 == -1 && i2 == -1)

@@ -121,7 +117,8 @@ int versioncmp(const char *s1, const char *s2)
 		initialized = 1;
 		prereleases = git_config_get_value_multi("versionsort.prereleasesuffix");
 	}
-	if (prereleases && swap_prereleases(p1 - 1, p2 - 1, &diff))
+	if (prereleases && swap_prereleases(s1, s2, (const char *) p1 - s1 - 1,
+					    &diff))
 		return diff;
 
 	state = result_type[state * 3 + (((c2 == '0') + (isdigit (c2) != 0)))];

2.11.0.78.g5a2d011

Version sort with prerelease reordering sometimes puts tagnames in the wrong order, when the common part of two compared tagnames overlaps with the leading character(s) of one or more configured prerelease suffixes. Note the position of "v2.1.0-beta-1":

  $ git -c versionsort.prereleaseSuffix=-beta \
        tag -l --sort=version:refname v2.1.*
  v2.1.0-beta-2
  v2.1.0-beta-3
  v2.1.0
  v2.1.0-RC1
  v2.1.0-RC2
  v2.1.0-beta-1
  v2.1.1
  v2.1.2

The reason is that when comparing a pair of tagnames, first versioncmp() looks for the first different character in a pair of tagnames, and then the swap_prereleases() helper function looks for a configured prerelease suffix _starting at_ that character. Thus, when in the above example the sorting algorithm happens to compare the tagnames "v2.1.0-beta-1" and "v2.1.0-RC2", swap_prereleases() tries to match the suffix "-beta" against "beta-1" to no avail, and the two tagnames erroneously end up being ordered lexicographically.

To fix this issue change swap_prereleases() to look for configured prerelease suffixes _containing_ the position of that first different character.

Care must be taken, when a configured suffix is longer than the tagnames' common part up to the first different character, to avoid reading memory before the beginning of the tagnames. Add a test that uses an exceptionally long prerelease suffix to check for this, in the hope that in case of a regression the illegal memory access causes a segfault in 'git tag' on one of the commonly used platforms (the test happens to pass successfully on my Linux system with the safety check removed), or at least makes valgrind complain.

Under some circumstances it's possible that more than one prerelease suffixes can be found in the same tagname around that first different character. With this simple bugfix patch such a tagname is sorted according to the contained suffix that comes first in the configuration for now. This is less than ideal in some cases, and the following patch will take care of those.

---
 Documentation/config.txt |  8 ++++++--
 t/t7004-tag.sh           |  9 +++++++--
 versioncmp.c             | 28 +++++++++++++++++++++-------
 3 files changed, 34 insertions(+), 11 deletions(-)

index 0bcb6790d..c1a9616e9 100644
@@ -3008,8 +3008,12 @@ versionsort.prereleaseSuffix::
 This variable can be specified multiple times, once per suffix. The
 order of suffixes in the config file determines the sorting order
 (e.g. if "-pre" appears before "-rc" in the config file then 1.0-preXX
-is sorted before 1.0-rcXX). The sorting order between different
-suffixes is undefined if they are in multiple config files.
+is sorted before 1.0-rcXX).
+If more than one suffixes match the same tagname, then that tagname will
+be sorted according to the matching suffix which comes first in the
+configuration.
+The sorting order between different suffixes is undefined if they are
+in multiple config files.
 
 web.browser::
 	Specify a web browser that may be used by some commands.

index 6445aae29..c7aaace8c 100755
@@ -1538,7 +1538,7 @@ test_expect_success 'reverse version sort with prerelease reordering' '
 	test_cmp expect actual
 '
 
-test_expect_failure 'version sort with prerelease reordering and common leading character' '
+test_expect_success 'version sort with prerelease reordering and common leading character' '
 	test_config versionsort.prereleaseSuffix -before &&
 	git tag foo1.7-before1 &&
 	git tag foo1.7 &&

@@ -1552,7 +1552,7 @@ test_expect_failure 'version sort with prerelease reordering and common leading
 	test_cmp expect actual
 '
 
-test_expect_failure 'version sort with prerelease reordering, multiple suffixes and common leading character' '
+test_expect_success 'version sort with prerelease reordering, multiple suffixes and common leading character' '
 	test_config versionsort.prereleaseSuffix -before &&
 	git config --add versionsort.prereleaseSuffix -after &&
 	git tag -l --sort=version:refname "foo1.7*" >actual &&

@@ -1564,6 +1564,11 @@ test_expect_failure 'version sort with prerelease reordering, multiple suffixes
 	test_cmp expect actual
 '
 
+test_expect_success 'version sort with very long prerelease suffix' '
+	test_config versionsort.prereleaseSuffix -very-looooooooooooooooooooooooong-prerelease-suffix &&
+	git tag -l --sort=version:refname
+'
+
 run_with_limited_stack () {
 	(ulimit -s 128 && "$@")
 }

index a55c23ad5..f86ac562e 100644
@@ -26,12 +26,15 @@ static int initialized;
 
 /*
  * off is the offset of the first different character in the two strings
- * s1 and s2. If either s1 or s2 contains a prerelease suffix starting
- * at that offset, it will be forced to be on top.
+ * s1 and s2. If either s1 or s2 contains a prerelease suffix containing
+ * that offset, then that string will be forced to be on top.
  *
- * If both s1 and s2 contain a (different) suffix at that position,
+ * If both s1 and s2 contain a (different) suffix around that position,
  * their order is determined by the order of those two suffixes in the
  * configuration.
+ * If any of the strings contains more than one different suffixes around
+ * that position, then that string is sorted according to the contained
+ * suffix which comes first in the configuration.
  *
  * Return non-zero if *diff contains the return value for versioncmp()
  */

@@ -44,10 +47,21 @@ static int swap_prereleases(const char *s1,
 
 	for (i = 0; i < prereleases->nr; i++) {
 		const char *suffix = prereleases->items[i].string;
-		if (i1 == -1 && starts_with(s1 + off, suffix))
-			i1 = i;
-		if (i2 == -1 && starts_with(s2 + off, suffix))
-			i2 = i;
+		int j, start, suffix_len = strlen(suffix);
+		if (suffix_len < off)
+			start = off - suffix_len + 1;
+		else
+			start = 0;
+		for (j = start; j <= off; j++)
+			if (i1 == -1 && starts_with(s1 + j, suffix)) {
+				i1 = i;
+				break;
+			}
+		for (j = start; j <= off; j++)
+			if (i2 == -1 && starts_with(s2 + j, suffix)) {
+				i2 = i;
+				break;
+			}
 	}
 	if (i1 == -1 && i2 == -1)
 		return 0;

2.11.0.78.g5a2d011

The caller has to compute it anyway, because it must deal with all the cases when the two compared tagnames are not reordered based on their (prerelease)suffix.

Sure.

When comparing tagnames, it is possible that a tagname contains more than one of the configured prerelease suffixes around the first different character. After fixing a bug in the previous commit such a tagname is sorted according to the contained suffix which comes first in the configuration. This is, however, not quite the right thing to do in the following corner cases:

1. $ git -c versionsort.suffix=-bar
-c versionsort.suffix=-foo-baz
-c versionsort.suffix=-foo-bar
tag -l --sort=version:refname 'v1*'
v1.0-foo-bar
v1.0-foo-baz

The suffix of the tagname 'v1.0-foo-bar' is clearly '-foo-bar', so it should be listed last. However, as it also contains '-bar' around the first different character, it is listed first instead, because that '-bar' suffix comes first the configuration.

2. One of the configured suffixes starts with the other:

       $ git -c versionsort.prereleasesuffix=-pre \
             -c versionsort.prereleasesuffix=-prerelease \
             tag -l --sort=version:refname 'v2*'
       v2.0-prerelease1
       v2.0-pre1
       v2.0-pre2

Here the tagname 'v2.0-prerelease1' should be the last. When comparing 'v2.0-pre1' and 'v2.0-prerelease1' the first different characters are '1' and 'r', respectively. Since this first different character must be part of the configured suffix, the '-pre' suffix is not recognized in the first tagname. OTOH, the '-prerelease' suffix is properly recognized in 'v2.0-prerelease1', thus it is listed first.

Improve version sort in these corner cases, and

- look for a configured prerelease suffix containing the first different character or ending right before it, so the '-pre' suffixes are recognized in case (2). This also means that when comparing tagnames 'v2.0-pre1' and 'v2.0-pre2', swap_prereleases() would find the '-pre' suffix in both, but then it will return "undecided" and the caller will do the right thing by sorting based in '1' and '2'.

- If the tagname contains more than one suffix, then give precedence to the contained suffix that starts at the earliest offset in the tagname to address (1).

- If there are more than one suffixes starting at that earliest position, then give precedence to the longest of those suffixes, thus ensuring that in (2) the tagname 'v2.0-prerelease1' won't be sorted based on the '-pre' suffix.

Add tests for these corner cases and adjust the documentation accordingly.

---
 Documentation/config.txt |  6 ++++--
 t/t7004-tag.sh           | 31 +++++++++++++++++++++++++++++++
 versioncmp.c             | 33 +++++++++++++++++++++++++--------
 3 files changed, 60 insertions(+), 10 deletions(-)

index c1a9616e9..58009c70c 100644
@@ -3010,8 +3010,10 @@ order of suffixes in the config file determines the sorting order
 (e.g. if "-pre" appears before "-rc" in the config file then 1.0-preXX
 is sorted before 1.0-rcXX).
 If more than one suffixes match the same tagname, then that tagname will
-be sorted according to the matching suffix which comes first in the
-configuration.
+be sorted according to the suffix which starts at the earliest position in
+the tagname.  If more than one different matching suffixes start at
+that earliest position, then that tagname will be sorted according to the
+longest of those suffixes.
 The sorting order between different suffixes is undefined if they are
 in multiple config files.
 

index c7aaace8c..e2efe312d 100755
@@ -1564,6 +1564,37 @@ test_expect_success 'version sort with prerelease reordering, multiple suffixes
 	test_cmp expect actual
 '
 
+test_expect_success 'version sort with prerelease reordering, multiple suffixes match the same tag' '
+	test_config versionsort.prereleaseSuffix -bar &&
+	git config --add versionsort.prereleaseSuffix -foo-baz &&
+	git config --add versionsort.prereleaseSuffix -foo-bar &&
+	git tag foo1.8-foo-bar &&
+	git tag foo1.8-foo-baz &&
+	git tag foo1.8 &&
+	git tag -l --sort=version:refname "foo1.8*" >actual &&
+	cat >expect <<-\EOF &&
+	foo1.8-foo-baz
+	foo1.8-foo-bar
+	foo1.8
+	EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'version sort with prerelease reordering, multiple suffixes match starting at the same position' '
+	test_config versionsort.prereleaseSuffix -pre &&
+	git config --add versionsort.prereleaseSuffix -prerelease &&
+	git tag foo1.9-pre1 &&
+	git tag foo1.9-pre2 &&
+	git tag foo1.9-prerelease1 &&
+	git tag -l --sort=version:refname "foo1.9*" >actual &&
+	cat >expect <<-\EOF &&
+	foo1.9-pre1
+	foo1.9-pre2
+	foo1.9-prerelease1
+	EOF
+	test_cmp expect actual
+'
+
 test_expect_success 'version sort with very long prerelease suffix' '
 	test_config versionsort.prereleaseSuffix -very-looooooooooooooooooooooooong-prerelease-suffix &&
 	git tag -l --sort=version:refname

index f86ac562e..ae0a9199b 100644
@@ -27,14 +27,18 @@ static int initialized;
 /*
  * off is the offset of the first different character in the two strings
  * s1 and s2. If either s1 or s2 contains a prerelease suffix containing
- * that offset, then that string will be forced to be on top.
+ * that offset or a suffix ends right before that offset, then that
+ * string will be forced to be on top.
  *
  * If both s1 and s2 contain a (different) suffix around that position,
  * their order is determined by the order of those two suffixes in the
  * configuration.
  * If any of the strings contains more than one different suffixes around
  * that position, then that string is sorted according to the contained
- * suffix which comes first in the configuration.
+ * suffix which starts at the earliest offset in that string.
+ * If more than one different contained suffixes start at that earliest
+ * offset, then that string is sorted according to the longest of those
+ * suffixes.
  *
  * Return non-zero if *diff contains the return value for versioncmp()
  */

@@ -44,27 +48,40 @@ static int swap_prereleases(const char *s1,
 			    int *diff)
 {
 	int i, i1 = -1, i2 = -1;
+	int start_at1 = off, start_at2 = off, match_len1 = -1, match_len2 = -1;
 
 	for (i = 0; i < prereleases->nr; i++) {
 		const char *suffix = prereleases->items[i].string;
-		int j, start, suffix_len = strlen(suffix);
+		int j, start, end, suffix_len = strlen(suffix);
 		if (suffix_len < off)
-			start = off - suffix_len + 1;
+			start = off - suffix_len;
 		else
 			start = 0;
-		for (j = start; j <= off; j++)
-			if (i1 == -1 && starts_with(s1 + j, suffix)) {
+		end = match_len1 < suffix_len ? start_at1 : start_at1-1;
+		for (j = start; j <= end; j++)
+			if (starts_with(s1 + j, suffix)) {
 				i1 = i;
+				start_at1 = j;
+				match_len1 = suffix_len;
 				break;
 			}
-		for (j = start; j <= off; j++)
-			if (i2 == -1 && starts_with(s2 + j, suffix)) {
+		end = match_len2 < suffix_len ? start_at2 : start_at2-1;
+		for (j = start; j <= end; j++)
+			if (starts_with(s2 + j, suffix)) {
 				i2 = i;
+				start_at2 = j;
+				match_len2 = suffix_len;
 				break;
 			}
 	}
 	if (i1 == -1 && i2 == -1)
 		return 0;
+	if (i1 == i2)
+		/* Found the same suffix in both, e.g. "-rc" in "v1.0-rcX"
+		 * and "v1.0-rcY": the caller should decide based on "X"
+		 * and "Y". */
+		return 0;
+
 	if (i1 >= 0 && i2 >= 0)
 		*diff = i1 - i2;
 	else if (i1 >= 0)

2.11.0.78.g5a2d011

As the number of identical steps to be done for both tagnames grows, extract them into a helper function, with the additional benefit that the conditionals near the end of swap_prereleases() will use more meaningful variable names.

---

I was not particularly happy with the amount of code duplication this series added to swap_prereleases() in patches 5 and 6, hence this bit of refactoring. Which I'm not particularly happy with either, because, well, look at that diffstat.

I don't have strong feelings either way, but here it is, take it or leave it.

 versioncmp.c | 62 ++++++++++++++++++++++++++++++++++++------------------------
 1 file changed, 37 insertions(+), 25 deletions(-)

index 62c8d69dc..601ceddef 100644
@@ -24,6 +24,29 @@
 static const struct string_list *prereleases;
 static int initialized;
 
+struct suffix_match {
+	int conf_pos;
+	int start;
+	int len;
+};
+
+static void find_better_matching_suffix(const char *tagname, const char *suffix,
+					int suffix_len, int start, int conf_pos,
+					struct suffix_match *match)
+{
+	/* A better match either starts earlier or starts at the same offset
+	 * but is longer. */
+	int end = match->len < suffix_len ? match->start : match->start-1;
+	int i;
+	for (i = start; i <= end; i++)
+		if (starts_with(tagname + i, suffix)) {
+			match->conf_pos = conf_pos;
+			match->start = i;
+			match->len = suffix_len;
+			break;
+		}
+}
+
 /*
  * off is the offset of the first different character in the two strings
  * s1 and s2. If either s1 or s2 contains a prerelease suffix containing

@@ -47,46 +70,35 @@ static int swap_prereleases(const char *s1,
 			    int off,
 			    int *diff)
 {
-	int i, i1 = -1, i2 = -1;
-	int start_at1 = off, start_at2 = off, match_len1 = -1, match_len2 = -1;
+	int i;
+	struct suffix_match match1 = { -1, off, -1 };
+	struct suffix_match match2 = { -1, off, -1 };
 
 	for (i = 0; i < prereleases->nr; i++) {
 		const char *suffix = prereleases->items[i].string;
-		int j, start, end, suffix_len = strlen(suffix);
+		int start, suffix_len = strlen(suffix);
 		if (suffix_len < off)
 			start = off - suffix_len;
 		else
 			start = 0;
-		end = match_len1 < suffix_len ? start_at1 : start_at1-1;
-		for (j = start; j <= end; j++)
-			if (starts_with(s1 + j, suffix)) {
-				i1 = i;
-				start_at1 = j;
-				match_len1 = suffix_len;
-				break;
-			}
-		end = match_len2 < suffix_len ? start_at2 : start_at2-1;
-		for (j = start; j <= end; j++)
-			if (starts_with(s2 + j, suffix)) {
-				i2 = i;
-				start_at2 = j;
-				match_len2 = suffix_len;
-				break;
-			}
+		find_better_matching_suffix(s1, suffix, suffix_len, start,
+					    i, &match1);
+		find_better_matching_suffix(s2, suffix, suffix_len, start,
+					    i, &match2);
 	}
-	if (i1 == -1 && i2 == -1)
+	if (match1.conf_pos == -1 && match2.conf_pos == -1)
 		return 0;
-	if (i1 == i2)
+	if (match1.conf_pos == match2.conf_pos)
 		/* Found the same suffix in both, e.g. "-rc" in "v1.0-rcX"
 		 * and "v1.0-rcY": the caller should decide based on "X"
 		 * and "Y". */
 		return 0;
 
-	if (i1 >= 0 && i2 >= 0)
-		*diff = i1 - i2;
-	else if (i1 >= 0)
+	if (match1.conf_pos >= 0 && match2.conf_pos >= 0)
+		*diff = match1.conf_pos - match2.conf_pos;
+	else if (match1.conf_pos >= 0)
 		*diff = -1;
-	else /* if (i2 >= 0) */
+	else /* if (match2.conf_pos >= 0) */
 		*diff = 1;
 	return 1;
 }

2.11.0.78.g5a2d011

The 'versionsort.prereleaseSuffix' configuration variable, as its name suggests, is supposed to only deal with tagnames with prerelease suffixes, and allows sorting those prerelease tags in a user-defined order before the suffixless main release tag, instead of sorting them simply lexicographically.

However, the previous changes in this series resulted in an interesting and useful property of version sort:

- The empty string as a configured suffix matches all tagnames, including tagnames without any suffix, but

- tagnames containing a "real" configured suffix are still ordered according to that real suffix, because any longer suffix takes precedence over the empty string.

Exploiting this property we can easily generalize suffix reordering and specify the order of tags with given suffixes not only before but even after a main release tag by using the empty suffix to denote the position of the main release tag, without any algorithm changes:

  $ git -c versionsort.prereleaseSuffix=-alpha \
        -c versionsort.prereleaseSuffix=-beta \
        -c versionsort.prereleaseSuffix="" \
        -c versionsort.prereleaseSuffix=-gamma \
        -c versionsort.prereleaseSuffix=-delta \
        tag -l --sort=version:refname 'v3.0*'
  v3.0-alpha1
  v3.0-beta1
  v3.0
  v3.0-gamma1
  v3.0-delta1

Since 'versionsort.prereleaseSuffix' is not a fitting name for a configuration variable to control this more general suffix reordering, introduce the new variable 'versionsort.suffix'. Still keep the old configuration variable name as a deprecated alias, though, to avoid suddenly breaking setups already using it. Ignore the old variable if both old and new configuration variables are set, but emit a warning so users will be aware of it and can fix their configuration. Extend the documentation to describe and add a test to check this more general behavior.

Note: since the empty suffix matches all tagnames, tagnames with suffixes not included in the configuration are listed together with the suffixless main release tag, ordered lexicographically right after that, i.e. before tags with suffixes listed in the configuration following the empty suffix.

---
 Documentation/config.txt  | 36 ++++++++++++++++++++++++++----------
 Documentation/git-tag.txt |  4 ++--
 t/t7004-tag.sh            | 35 +++++++++++++++++++++++++++++++++++
 versioncmp.c              |  9 ++++++++-
 4 files changed, 71 insertions(+), 13 deletions(-)

index 58009c70c..ae85d4b9a 100644
@@ -2999,16 +2999,32 @@ user.signingKey::
 	This option is passed unchanged to gpg's --local-user parameter,
 	so you may specify a key using any method that gpg supports.
 
-versionsort.prereleaseSuffix::
-	When version sort is used in linkgit:git-tag[1], prerelease
-	tags (e.g. "1.0-rc1") may appear after the main release
-	"1.0". By specifying the suffix "-rc" in this variable,
-	"1.0-rc1" will appear before "1.0".
-+
-This variable can be specified multiple times, once per suffix. The
-order of suffixes in the config file determines the sorting order
-(e.g. if "-pre" appears before "-rc" in the config file then 1.0-preXX
-is sorted before 1.0-rcXX).
+versionsort.prereleaseSuffix (deprecated)::
+	Deprecated alias for `versionsort.suffix`.  Ignored if
+	`versionsort.suffix` is set.
+
+versionsort.suffix::
+	Even when version sort is used in linkgit:git-tag[1], tagnames
+	with the same base version but different suffixes are still sorted
+	lexicographically, resulting e.g. in prerelease tags appearing
+	after the main release (e.g. "1.0-rc1" after "1.0").  This
+	variable can be specified to determine the sorting order of tags
+	with different suffixes.
++
+By specifying a single suffix in this variable, any tagname containing
+that suffix will appear before the corresponding main release.  E.g. if
+the variable is set to "-rc", then all "1.0-rcX" tags will appear before
+"1.0".  If specified multiple times, once per suffix, then the order of
+suffixes in the configuration will determine the sorting order of tagnames
+with those suffixes.  E.g. if "-pre" appears before "-rc" in the
+configuration, then all "1.0-preX" tags will be listed before any
+"1.0-rcX" tags.  The placement of the main release tag relative to tags
+with various suffixes can be determined by specifying the empty suffix
+among those other suffixes.  E.g. if the suffixes "-rc", "", "-ck" and
+"-bfs" appear in the configuration in this order, then all "v4.8-rcX" tags
+are listed first, followed by "v4.8", then "v4.8-ckX" and finally
+"v4.8-bfsX".
++
 If more than one suffixes match the same tagname, then that tagname will
 be sorted according to the suffix which starts at the earliest position in
 the tagname.  If more than one different matching suffixes start at

index 7ecca8e24..19990850d 100644
@@ -101,8 +101,8 @@ OPTIONS
 	multiple times, in which case the last key becomes the primary
 	key. Also supports "version:refname" or "v:refname" (tag
 	names are treated as versions). The "version:refname" sort
-	order can also be affected by the
-	"versionsort.prereleaseSuffix" configuration variable.
+	order can also be affected by the "versionsort.suffix"
+	configuration variable.
 	The keys supported are the same as those in `git for-each-ref`.
 	Sort order defaults to the value configured for the `tag.sort`
 	variable if it exists, or lexicographic order otherwise. See

index e2efe312d..bdd28dad1 100755
@@ -1595,6 +1595,41 @@ test_expect_success 'version sort with prerelease reordering, multiple suffixes
 	test_cmp expect actual
 '
 
+test_expect_success 'version sort with general suffix reordering' '
+	test_config versionsort.suffix -alpha &&
+	git config --add versionsort.suffix -beta &&
+	git config --add versionsort.suffix ""  &&
+	git config --add versionsort.suffix -gamma &&
+	git config --add versionsort.suffix -delta &&
+	git tag foo1.10-alpha &&
+	git tag foo1.10-beta &&
+	git tag foo1.10-gamma &&
+	git tag foo1.10-delta &&
+	git tag foo1.10-unlisted-suffix &&
+	git tag -l --sort=version:refname "foo1.10*" >actual &&
+	cat >expect <<-\EOF &&
+	foo1.10-alpha
+	foo1.10-beta
+	foo1.10
+	foo1.10-unlisted-suffix
+	foo1.10-gamma
+	foo1.10-delta
+	EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'versionsort.suffix overrides versionsort.prereleaseSuffix' '
+	test_config versionsort.suffix -before &&
+	test_config versionsort.prereleaseSuffix -after &&
+	git tag -l --sort=version:refname "foo1.7*" >actual &&
+	cat >expect <<-\EOF &&
+	foo1.7-before1
+	foo1.7
+	foo1.7-after1
+	EOF
+	test_cmp expect actual
+'
+
 test_expect_success 'version sort with very long prerelease suffix' '
 	test_config versionsort.prereleaseSuffix -very-looooooooooooooooooooooooong-prerelease-suffix &&
 	git tag -l --sort=version:refname

index ae0a9199b..62c8d69dc 100644
@@ -145,8 +145,15 @@ int versioncmp(const char *s1, const char *s2)
 	}
 
 	if (!initialized) {
+		const struct string_list *deprecated_prereleases;
 		initialized = 1;
-		prereleases = git_config_get_value_multi("versionsort.prereleasesuffix");
+		prereleases = git_config_get_value_multi("versionsort.suffix");
+		deprecated_prereleases = git_config_get_value_multi("versionsort.prereleasesuffix");
+		if (prereleases) {
+			if (deprecated_prereleases)
+				warning("ignoring versionsort.prereleasesuffix because versionsort.suffix is set");
+		} else
+			prereleases = deprecated_prereleases;
 	}
 	if (prereleases && swap_prereleases(s1, s2, (const char *) p1 - s1 - 1,
 					    &diff))

2.11.0.78.g5a2d011

Thanks. Will comment on the individual patches later, but the end result looks very nice.

The whole approach taken by the suffix code (before your patches) leaves me with the nagging feeling that the comparison is not always going to be transitive (i.e., that "a < b && b < c" does not always imply "a < c"), which is going to cause nonsensical sorting results.

And that may be part of the issue your 6/7 fixes.

I spent some time playing with this the other day, though, and couldn't come up with a specific example that fails the condition above.

It just seems like the whole thing would conceptually easier if we pre-parsed the versions into a sequence of elements, then the comparison between any two elements would just walk that sequence. The benefit there is that you can implement whatever rules you like for the parsing (like "prefer longer suffixes to shorter"), but you know the comparison will always be consistent.

It would also be more efficient, I think (it seems like the sort is O(nr_tags * lg(nr_tags) * nr_suffixes) due to parsing suffixes in the comparator). Though that probably doesn't matter much in practice.

I dunno. I think maybe your 6/7 has converged on an equivalent behavior. And I am certainly not volunteering to re-write it, so if what you have works, I'm not opposed to it.

-Peff

I also had worries about transitiveness but couldn't break it after trying for some time. I find your pre-parsing suggestion a great one, not from the point of view of performance, but because I would imagine that the resulting logic would become a lot easier to understand.

I considered parsing tagnames into prefix, version number and suffix, and then work from that, but decided against it.

versioncmp() is taken from glibc, so I assume that it's thoroughly tested, even in corner cases (e.g. multiple leading zeros). Furthermore, I think it's a good thing that by default (i.e. without suffix reordering) our version sort orders the same way as glibc's version sort does. Introducing a different algorithm would risk bugs in the more subtle cases.

Then there are all the weird release suffixes out there, and I didn't want to decide on a policy for splitting them sanely; don't know whether there exist any universal rules for this splitting at all. E.g. one of the packages here has the following version (let's ignore the fact that because of the '~' this is an invalid refname in git):

1.1.0~rc1-2ubuntu7-1linuxmint1

Now, it's clear that the version number is "1.1.0", and the user should configure the suffix "~rc" for prerelease reordering. But what about the rest? How should we split it "into a sequence of elements", is it { "1.1.0", "~rc1", "-2ubuntu7", "-1linuxmint1" } or { "1.1.0", "~rc1-2", "ubuntu7-1", "linuxmint1" }?
What if there is a hard-working developer who is involved in a lot of Debian derivatives (and derivatives of derivatives...), and, for whatever reason, wants to put derivative-specific versions in a particular order? With my series, or conceptually even with master if it weren't buggy, it's possible to specify the order of suffixes of suffixes, and that dev could do this:

  $ git -c versionsort.suffix=-rc
        -c versionsort.suffix=linuxmint
        -c versionsort.suffix=YADoaDD
        tag -l --sort=version:refname
  '1.1.0*'
  1.1.0-rc1-2ubuntu7-1linuxmint1
  1.1.0-rc1-2ubuntu7-1YADoaDD2
  1.1.0
  1.1.0-2ubuntu7-1linuxmint1
  1.1.0-2ubuntu7-1YADoaDD2

and would get Linux Mint-specific tags before "Yet Another Derivative of a Debian Derivative"-specific ones. Not sure whether this is relevant in practice, but I think it's a nice property nonetheless.

(Btw, just for fun, I also found a package version 2.0.0~beta2+isreally1.8.6-0ubuntu1. "isreally". Oh yeah :)

I don't think there will be more than only a few configured suffixes in any repository. However, if you consider O as "number of starts_with() invocations", then there is an additional suffix_length factor. But then again, these suffixes tend to be short.

Fair enough. If it's working, I agree there is risk in changing things. And if you're willing to deal with the bugs, then I'm happy to stand back. :)

I have a hunch that any policy you'd have to set for splitting is going to end up becoming a policy you'll have to use when comparing (or you risk violating the transitivity of your comparison function).

But that's just a hunch, not a proof. Again, I'm happy to defer to you if you're the one working on it.

-Peff

Yes, yes you are the best. Workaround works, tyvm. I was heading in that direction, too, but never thought to remove leading dash on the alternates - instead I tried "-b", "-R" and similar just to see what happens.