2.10.0: multiple versionsort.prereleasesuffix buggy?

2.10.0: multiple versionsort.prereleasesuffix buggy?

[Leho Kraav (Conversion Ready)]

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

Re: 2.10.0: multiple versionsort.prereleasesuffix buggy?

[Jeff King]

On Tue, Sep 06, 2016 at 01:42:28AM +0300, Leho Kraav (Conversion Ready) wrote:

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

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

Re: 2.10.0: multiple versionsort.prereleasesuffix buggy?

[SZEDER Gábor]

> On Tue, Sep 06, 2016 at 01:42:28AM +0300, Leho Kraav (Conversion Ready) wrote:
> 
> > 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.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
> 
> 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.

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

Re: 2.10.0: multiple versionsort.prereleasesuffix buggy?

[Jeff King]

On Tue, Sep 06, 2016 at 03:07:59AM +0200, SZEDER Gábor wrote:

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

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

Re: 2.10.0: multiple versionsort.prereleasesuffix buggy?

[Leho Kraav (Conversion Ready)]

On 06.09.2016 04:07, SZEDER Gábor wrote:
>
> [versionsort]
> 	prereleasesuffix = beta
> 	prereleasesuffix = -beta
> 	prereleasesuffix = RC
> 	prereleasesuffix = -RC
>
> Best,
> Gábor

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.

Re: 2.10.0: multiple versionsort.prereleasesuffix buggy?

[SZEDER Gábor]

Hi,


Quoting Jeff King <peff@peff.net>:

> On Tue, Sep 06, 2016 at 03:07:59AM +0200, SZEDER Gábor wrote:
>
>>> 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.
>>
>> 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).
>
> 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.

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

[PATCH 0/5] Fix version sort prerelease reordering bug

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

[PATCH 1/5] t7004-tag: delete unnecessary tags with test_when_finished

[SZEDER Gábor]

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.

Signed-off-by: SZEDER Gábor <szeder@ira.uka.de>
---
 t/t7004-tag.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index 8b0f71a2ac15..396cffeeb5ad 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -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

[PATCH 2/5] t7004-tag: use test_config helper

[SZEDER Gábor]

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

Signed-off-by: SZEDER Gábor <szeder@ira.uka.de>
---
 t/t7004-tag.sh | 23 ++++++++++-------------
 1 file changed, 10 insertions(+), 13 deletions(-)

diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index 396cffeeb5ad..920a1b4b2e58 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -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

[PATCH 3/5] t7004-tag: add version sort tests to show prerelease reordering issues

[SZEDER Gábor]

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.

Signed-off-by: SZEDER Gábor <szeder@ira.uka.de>
---
 t/t7004-tag.sh | 62 +++++++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 48 insertions(+), 14 deletions(-)

diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index 920a1b4b2e58..d69ac4940388 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -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

[PATCH 4/5] versioncmp: pass full tagnames to swap_prereleases()

[SZEDER Gábor]

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.

Signed-off-by: SZEDER Gábor <szeder@ira.uka.de>
---
 versioncmp.c | 28 ++++++++++++++--------------
 1 file changed, 14 insertions(+), 14 deletions(-)

diff --git a/versioncmp.c b/versioncmp.c
index 80bfd109fa12..fed02d2a2878 100644
--- a/versioncmp.c
+++ b/versioncmp.c
@@ -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

[PATCH 5/5] versioncmp: cope with common leading parts in versionsort.prereleaseSuffix

[SZEDER Gábor]

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.

Reported-by: Leho Kraav <leho@conversionready.com>
Signed-off-by: SZEDER Gábor <szeder@ira.uka.de>
---
 t/t7004-tag.sh |  4 ++--
 versioncmp.c   | 24 +++++++++++++++++++-----
 2 files changed, 21 insertions(+), 7 deletions(-)

diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index d69ac4940388..f0cfe1fa3d8b 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -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 &&
diff --git a/versioncmp.c b/versioncmp.c
index fed02d2a2878..87b49a622423 100644
--- a/versioncmp.c
+++ b/versioncmp.c
@@ -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

Re: [PATCH 5/5] versioncmp: cope with common leading parts in versionsort.prereleaseSuffix

[SZEDER Gábor]

Quoting SZEDER Gábor <szeder@ira.uka.de>:

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

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

Re: [PATCH 4/5] versioncmp: pass full tagnames to swap_prereleases()

[Junio C Hamano]

SZEDER Gábor <szeder@ira.uka.de> writes:

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

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

Re: [PATCH 4/5] versioncmp: pass full tagnames to swap_prereleases()

[SZEDER Gábor]

Quoting Junio C Hamano <gitster@pobox.com>:

> SZEDER Gábor <szeder@ira.uka.de> writes:
>
>> - * 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.
>
> "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?

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

Re: [PATCH 4/5] versioncmp: pass full tagnames to swap_prereleases()

[Junio C Hamano]

SZEDER Gábor <szeder@ira.uka.de> writes:

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

Concurred.  Let's lose this confusing statement.

Thanks.

Re: [PATCH 5/5] versioncmp: cope with common leading parts in versionsort.prereleaseSuffix

[Duy Nguyen]

On Wed, Sep 7, 2016 at 10:48 PM, SZEDER Gábor <szeder@ira.uka.de> wrote:
> 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.

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

Re: [PATCH 5/5] versioncmp: cope with common leading parts in versionsort.prereleaseSuffix

[SZEDER Gábor]

Quoting SZEDER Gábor <szeder@ira.uka.de>:

> Quoting SZEDER Gábor <szeder@ira.uka.de>:
>
>> 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.
>
> 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.

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

Re: [PATCH 5/5] versioncmp: cope with common leading parts in versionsort.prereleaseSuffix

[Junio C Hamano]

SZEDER Gábor <szeder@ira.uka.de> writes:

> 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

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

Re: [PATCH 5/5] versioncmp: cope with common leading parts in versionsort.prereleaseSuffix

[SZEDER Gábor]

Quoting Junio C Hamano <gitster@pobox.com>:

> SZEDER Gábor <szeder@ira.uka.de> writes:
>
>> 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
>
> Assuming that gamma and delta are meant to indicate "these are
> post-release updates",

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.

> I think a mechanism that can yield the above
> result is fantastic ;-)

Heh.

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

Re: [PATCH 5/5] versioncmp: cope with common leading parts in versionsort.prereleaseSuffix

[Junio C Hamano]

SZEDER Gábor <szeder@ira.uka.de> writes:

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

Re: [PATCH 5/5] versioncmp: cope with common leading parts in versionsort.prereleaseSuffix

[Jacob Keller]

On Wed, Oct 5, 2016 at 3:15 PM, Junio C Hamano <gitster@pobox.com> wrote:
> SZEDER Gábor <szeder@ira.uka.de> writes:
>
>> 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

Re: [PATCH 5/5] versioncmp: cope with common leading parts in versionsort.prereleaseSuffix

[Duy Nguyen]

On Thu, Oct 6, 2016 at 7:40 AM, Jacob Keller <jacob.keller@gmail.com> wrote:
> On Wed, Oct 5, 2016 at 3:15 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> SZEDER Gábor <szeder@ira.uka.de> writes:
>>
>>> 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"?

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.

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

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

[PATCHv2 0/7] Fix and generalize version sort reordering

[SZEDER Gábor]

> After having slept on this a couple of times

After having slept on it a few (erm...) more 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.

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.

> 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

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


diff --git a/Documentation/config.txt b/Documentation/config.txt
index 0bcb6790d..c1a9616e9 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -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.
diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index f0cfe1fa3..c7aaace8c 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -1511,14 +1511,14 @@ test_expect_success 'invalid sort parameter in configuratoin' '
 '
 
 test_expect_success 'version sort with prerelease reordering' '
-	test_config versionsort.prereleaseSuffix -beta &&
-	git tag foo1.6-beta1 &&
-	git tag foo1.6-beta2 &&
+	test_config 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.10
 	EOF
@@ -1526,54 +1526,49 @@ test_expect_success 'version sort with prerelease reordering' '
 '
 
 test_expect_success 'reverse version sort with prerelease reordering' '
-	test_config versionsort.prereleaseSuffix -beta &&
+	test_config versionsort.prereleaseSuffix -rc &&
 	git tag -l --sort=-version:refname "foo*" >actual &&
 	cat >expect <<-\EOF &&
 	foo1.10
 	foo1.6
-	foo1.6-beta2
-	foo1.6-beta1
+	foo1.6-rc2
+	foo1.6-rc1
 	foo1.3
 	EOF
 	test_cmp expect actual
 '
 
 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 &&
+	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.3
-	foo1.6-beta1
-	foo1.6-beta2
-	foo1.6
-	foo1.6-after1
-	foo1.10
+	foo1.7-before1
+	foo1.7
+	foo1.7-after1
 	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_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 &&
-	git tag foo1.6-RC2 &&
-	git tag -l --sort=version:refname "foo*" >actual &&
+	test_config versionsort.prereleaseSuffix -before &&
+	git config --add versionsort.prereleaseSuffix -after &&
+	git tag -l --sort=version:refname "foo1.7*" >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
+	foo1.7-before1
+	foo1.7-after1
+	foo1.7
 	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
+'
+
 run_with_limited_stack () {
 	(ulimit -s 128 && "$@")
 }
diff --git a/versioncmp.c b/versioncmp.c
index 87b49a622..f86ac562e 100644
--- a/versioncmp.c
+++ b/versioncmp.c
@@ -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;

[PATCHv2 1/7] t7004-tag: delete unnecessary tags with test_when_finished

[SZEDER Gábor]

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.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 t/t7004-tag.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index 8b0f71a2a..396cffeeb 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -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

[PATCHv2 2/7] t7004-tag: use test_config helper

[SZEDER Gábor]

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

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 t/t7004-tag.sh | 23 ++++++++++-------------
 1 file changed, 10 insertions(+), 13 deletions(-)

diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index 396cffeeb..920a1b4b2 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -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

[PATCHv2 3/7] t7004-tag: add version sort tests to show prerelease reordering issues

[SZEDER Gábor]

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.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 t/t7004-tag.sh | 36 ++++++++++++++++++++++++++++++------
 1 file changed, 30 insertions(+), 6 deletions(-)

diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index 920a1b4b2..6445aae29 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -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

[PATCHv2 4/7] versioncmp: pass full tagnames to swap_prereleases()

[SZEDER Gábor]

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.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 versioncmp.c | 29 +++++++++++++----------------
 1 file changed, 13 insertions(+), 16 deletions(-)

diff --git a/versioncmp.c b/versioncmp.c
index 80bfd109f..a55c23ad5 100644
--- a/versioncmp.c
+++ b/versioncmp.c
@@ -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

[PATCHv2 5/7] versioncmp: cope with common part overlapping with prerelease suffix

[SZEDER Gábor]

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.

Reported-by: Leho Kraav <leho@conversionready.com>
Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 Documentation/config.txt |  8 ++++++--
 t/t7004-tag.sh           |  9 +++++++--
 versioncmp.c             | 28 +++++++++++++++++++++-------
 3 files changed, 34 insertions(+), 11 deletions(-)

diff --git a/Documentation/config.txt b/Documentation/config.txt
index 0bcb6790d..c1a9616e9 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -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.
diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index 6445aae29..c7aaace8c 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -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 && "$@")
 }
diff --git a/versioncmp.c b/versioncmp.c
index a55c23ad5..f86ac562e 100644
--- a/versioncmp.c
+++ b/versioncmp.c
@@ -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

[PATCHv2 6/7] versioncmp: use earliest-longest contained suffix to determine sorting order

[SZEDER Gábor]

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.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 Documentation/config.txt |  6 ++++--
 t/t7004-tag.sh           | 31 +++++++++++++++++++++++++++++++
 versioncmp.c             | 33 +++++++++++++++++++++++++--------
 3 files changed, 60 insertions(+), 10 deletions(-)

diff --git a/Documentation/config.txt b/Documentation/config.txt
index c1a9616e9..58009c70c 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -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.
 
diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index c7aaace8c..e2efe312d 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -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
diff --git a/versioncmp.c b/versioncmp.c
index f86ac562e..ae0a9199b 100644
--- a/versioncmp.c
+++ b/versioncmp.c
@@ -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

[PATCHv2 7/7] versioncmp: generalize version sort suffix reordering

[SZEDER Gábor]

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.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 Documentation/config.txt  | 36 ++++++++++++++++++++++++++----------
 Documentation/git-tag.txt |  4 ++--
 t/t7004-tag.sh            | 35 +++++++++++++++++++++++++++++++++++
 versioncmp.c              |  9 ++++++++-
 4 files changed, 71 insertions(+), 13 deletions(-)

diff --git a/Documentation/config.txt b/Documentation/config.txt
index 58009c70c..ae85d4b9a 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -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
diff --git a/Documentation/git-tag.txt b/Documentation/git-tag.txt
index 7ecca8e24..19990850d 100644
--- a/Documentation/git-tag.txt
+++ b/Documentation/git-tag.txt
@@ -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
diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index e2efe312d..bdd28dad1 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -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
diff --git a/versioncmp.c b/versioncmp.c
index ae0a9199b..62c8d69dc 100644
--- a/versioncmp.c
+++ b/versioncmp.c
@@ -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

[PATCHv2 6.5/7] squash! versioncmp: use earliest-longest contained suffix to determine sorting order

[SZEDER Gábor]

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.

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---

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

diff --git a/versioncmp.c b/versioncmp.c
index 62c8d69dc..601ceddef 100644
--- a/versioncmp.c
+++ b/versioncmp.c
@@ -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

Re: [PATCHv2 7/7] versioncmp: generalize version sort suffix reordering

[Junio C Hamano]

SZEDER Gábor <szeder.dev@gmail.com> writes:

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

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

Re: [PATCHv2 5/7] versioncmp: cope with common part overlapping with prerelease suffix

[Junio C Hamano]

SZEDER Gábor <szeder.dev@gmail.com> writes:

> diff --git a/versioncmp.c b/versioncmp.c
> index a55c23ad5..f86ac562e 100644
> --- a/versioncmp.c
> +++ b/versioncmp.c
> @@ -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;

Now that this function has to rewind the beginning of the comparison
earlier than the given 'off', it makes me wonder if it still makes
sense for the caller to compute it in the first place.

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

Re: [PATCHv2 5/7] versioncmp: cope with common part overlapping with prerelease suffix

[SZEDER Gábor]

On Mon, Dec 12, 2016 at 10:27 PM, Junio C Hamano <gitster@pobox.com> wrote:
> SZEDER Gábor <szeder.dev@gmail.com> writes:
>
>> diff --git a/versioncmp.c b/versioncmp.c
>> index a55c23ad5..f86ac562e 100644
>> --- a/versioncmp.c
>> +++ b/versioncmp.c
>> @@ -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;
>
> Now that this function has to rewind the beginning of the comparison
> earlier than the given 'off', it makes me wonder if it still makes
> sense for the caller to compute it in the first place.

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.

Re: [PATCHv2 5/7] versioncmp: cope with common part overlapping with prerelease suffix

[Junio C Hamano]

SZEDER Gábor <szeder.dev@gmail.com> writes:

>>> -             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;
>>
>> Now that this function has to rewind the beginning of the comparison
>> earlier than the given 'off', it makes me wonder if it still makes
>> sense for the caller to compute it in the first place.
>
> 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.

Re: [PATCHv2 0/7] Fix and generalize version sort reordering

[Jeff King]

On Thu, Dec 08, 2016 at 03:23:54PM +0100, SZEDER Gábor wrote:

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

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

Re: [PATCHv2 0/7] Fix and generalize version sort reordering

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Thu, Dec 08, 2016 at 03:23:54PM +0100, SZEDER Gábor wrote:
>
>> > 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
>> 
>> 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.
>
> 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.

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.

Re: [PATCHv2 0/7] Fix and generalize version sort reordering

[SZEDER Gábor]

On Wed, Dec 14, 2016 at 6:08 PM, Jeff King <peff@peff.net> wrote:
> On Thu, Dec 08, 2016 at 03:23:54PM +0100, SZEDER Gábor wrote:
>
>> > 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
>>
>> 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.
>
> 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.

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

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

> 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

Re: [PATCHv2 0/7] Fix and generalize version sort reordering

[Jeff King]

On Tue, Dec 20, 2016 at 09:50:42AM +0100, SZEDER Gábor wrote:

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

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

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

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