maven-artifact ComparableVersion doesn't work well with java colllections sort algorithm timsort: Comparison method violates its general contract

Question

ComparableVersion offered by maven-artifact is used in my project to sort artifact by its version. For example, these versions is offered(should spilt by //).

0.0.1576817712//0.0.3//0.0.4//0.0.4.//0.0.4.1//0.0.4.2//0.0.4.3//0.0.4.4//0.0.4.5//0.0.5//0.0.5.1//0.0.5.2//0.0.5.3//0.0.5.4//0.0.6//0.0.7//0.0.8//0.1.0//0.1.2//0.1.2.1//0.1.2.2//0.1.2.3//0.1.2.4//0.1.2.5//0.1.2.6//0.1.2.7//0.1.2.8//0.1.3//0.1.3.1//0.1.3.2//0.1.3.3//0.1.4//0.1.4.1//0.1.4.2//0.1.4.3//0.1.4.4//0.1.4.5//0.1.4.6//0.1.4.7//0.1.4.8//0.1.4.9//0.1.5//0.1.7//0.1.7.1//0.1.7.2//0.1.7.3//0.1.7.4//0.1.7.5//0.1.7.6//0.1.7.7//0.1.8//0.1.9//0.1.9.1//0.1.9.11//0.1.9.12//0.1.9.13//0.1.9.2//0.1.9.3//0.1.9.8//0.1.9.9//0.1.9.9.1//1.0.0.1//1.0.0.2//1.0.0.3//1.0.0.3.1//1.0.0.4//1.0.0.5//0.0.0.1-SNAPSHOT//0.0.11-SNAPSHOT//0.0.1576066498-SNAPSHOT//0.0.1576066912-SNAPSHOT//0.0.1576209616-SNAPSHOT//0.0.1576677646-SNAPSHOT//0.0.1576722159-SNAPSHOT//0.0.1576732580-SNAPSHOT//0.0.1576737990-SNAPSHOT//0.0.1576757185-SNAPSHOT//0.0.1576812388-SNAPSHOT//0.0.1576817712-SNAPSHOT//0.0.1576821661-SNAPSHOT//0.0.1576821977-SNAPSHOT//0.0.1576825998-SNAPSHOT//0.0.1577182101-SNAPSHOT//0.0.1577266235-SNAPSHOT//0.0.1577267400-SNAPSHOT//0.0.1577268933-SNAPSHOT//0.0.2-SNAPSHOT//0.0.3-SNAPSHOT//0.0.4-SNAPSHOT//0.0.4.1-SNAPSHOT//0.0.4.2-SNAPSHOT//0.0.4.4-SNAPSHOT//0.0.4.5-SNAPSHOT//0.0.5-SNAPSHOT//0.0.5.11151113-SNAPSHOT//0.0.5.2-SNAPSHOT//0.0.5.2.1-SNAPSHOT//0.0.5.20180829-SNAPSHOT//0.0.5.20181115-SNAPSHOT//0.0.5.4-SNAPSHOT//0.0.5.4.181113-SNAPSHOT//0.0.5.5-SNAPSHOT//0.0.6-SNAPSHOT//0.0.7-SNAPSHOT//0.0.8-SNAPSHOT//0.0.9-SNAPSHOT//0.0.91576063257-SNAPSHOT//0.0.91576066026-SNAPSHOT//0.1.0-SNAPSHOT//0.1.1-SNAPSHOT//0.1.2-SNAPSHOT//0.1.2.2-SNAPSHOT//0.1.2.3-SNAPSHOT//0.1.2.4-SNAPSHOT//0.1.2.5-SNAPSHOT//0.1.2.6-SNAPSHOT//0.1.2.7-SNAPSHOT//0.1.3-SNAPSHOT//0.1.3.1-SNAPSHOT//0.1.3.3-SNAPSHOT//0.1.3.4-SNAPSHOT//0.1.4-SNAPSHOT//0.1.4.1-SNAPSHOT//0.1.4.4-SNAPSHOT//0.1.4.5-SNAPSHOT//0.1.4.6-SNAPSHOT//0.1.4.7-SNAPSHOT//0.1.4.9-SNAPSHOT//0.1.4.l-SNAPSHOT//0.1.4.y-SNAPSHOT//0.1.4.yl-SNAPSHOT//0.1.4.yy-SNAPSHOT//0.1.5-push-SNAPSHOT//0.1.5-SNAPSHOT//0.1.5.1-SNAPSHOT//0.1.5.2-SNAPSHOT//0.1.5.3-SNAPSHOT//0.1.5.4-SNAPSHOT//0.1.5.5-SNAPSHOT//0.1.5.6-SNAPSHOT//0.1.5.l-SNAPSHOT//0.1.5.testpush-SNAPSHOT//0.1.5.y-SNAPSHOT//0.1.5.yl-SNAPSHOT//0.1.6-SNAPSHOT//0.1.7-SNAPSHOT//0.1.7.1-SNAPSHOT//0.1.7.2-SNAPSHOT//0.1.7.3-SNAPSHOT//0.1.7.4-SNAPSHOT//0.1.7.6.1-SNAPSHOT//0.1.8-SNAPSHOT//0.1.9.15-SNAPSHOT//0.1.9.16-SNAPSHOT//0.1.9.2-SNAPSHOT//0.1.9.6-SNAPSHOT//0.1.9.7-SNAPSHOT//0.1.9.9.2-SNAPSHOT//0.1.9.9.3-SNAPSHOT//0.2.0-SNAPSHOT//1.0.0.0-SNAPSHOT//1.0.0.1-SNAPSHOT//1.0.0.2-SNAPSHOT//1.0.0.3-lv-SNAPSHOT//1.0.0.3-SNAPSHOT//1.0.0.4-SNAPSHOT//1.0.0.5-SNAPSHOT//1.0.0.6-SNAPSHOT//1.0.0.7-SNAPSHOT//1.0.0.8-SNAPSHOT//1.0.0.9-SNAPSHOT//1.0.1-SNAPSHOT//1.0.1.0-SNAPSHOT//1.0.1.1-SNAPSHOT//1.0.1.2-SNAPSHOT//1.0.1.3-SNAPSHOT//

And here is my code

String data = "...."; // the above string
String[] versions = data.split("//");
List<ComparableVersion> comparableVersions = Arrays.stream(versions).map(ComparableVersion::new).collect(Collectors.toList());
Collections.sort(comparableVersions);

And an error occured

java.lang.IllegalArgumentException: Comparison method violates its general contract!

    at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:422)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:222)
    at java.util.Arrays.sort(Arrays.java:1312)
    at java.util.Arrays.sort(Arrays.java:1506)
    at java.util.ArrayList.sort(ArrayList.java:1464)
    at java.util.Collections.sort(Collections.java:143)

1 I've already tried add different version of maven-artifact dependencies, but all with the same problem.

// version 3.8.6 3.8.7 and 3.6.3 are tried
<dependency>
   <groupId>org.apache.maven</groupId>
   <artifactId>maven-artifact</artifactId>
   <version>3.6.3</version>
</dependency>

2 Using LegacyMergeSort instead of timsort can solve the problem by adding -Djava.util.Arrays.useLegacyMergeSort=true to jvm params, but I don't want it to work on all the array.sort in my project.

So what's wrong with ComparableVersion working with timsort. And how can I find another way to solving this sorting problem. Thanks~

Which versions of maven-artifact have you tried, and what's the precise dependency? — tgdavies, Jan 13 '23 at 06:51
First question why do you like to use it? Second as question already which version do you use? A version does not contain `//` ?? — khmarbaise, Jan 13 '23 at 06:56
@tgdavies precise dependency and tried version is updated in question. — HHHHNNNNNNIIIII, Jan 13 '23 at 07:02
@khmarbaise Sorry for not expressing clearly, versions can be get like this String[] versions = data.split("//") — HHHHNNNNNNIIIII, Jan 13 '23 at 07:04
So you have an array of Strings but not an array of ComparableVersions; Every element of the array has to be using the constructor(if I correctly remember) of ComarableVersions and you can sort a list/array of ComparableVersions or there is a method (parseVersion)... — khmarbaise, Jan 13 '23 at 07:10
@khmarbaise Yes, I've add example code on question description. — HHHHNNNNNNIIIII, Jan 13 '23 at 07:37

score 1 · Answer 1 · answered Jan 13 '23 at 08:48

Make sure that you don't have any duplicate version numbers which have different string representations:

import org.apache.maven.artifact.versioning.ComparableVersion;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class Test2 {

    public static void main(String[] args) {
        String data = "0.0.1576817712//0.0.3//0.0.4//0.0.4.//0.0.4.1//0.0.4.2//0.0.4.3//0.0.4.4//0.0.4.5//0.0.5//0.0.5.1//0.0.5.2//0.0.5.3//0.0.5.4//0.0.6//0.0.7//0.0.8//0.1.0//0.1.2//0.1.2.1//0.1.2.2//0.1.2.3//0.1.2.4//0.1.2.5//0.1.2.6//0.1.2.7//0.1.2.8//0.1.3//0.1.3.1//0.1.3.2//0.1.3.3//0.1.4//0.1.4.1//0.1.4.2//0.1.4.3//0.1.4.4//0.1.4.5//0.1.4.6//0.1.4.7//0.1.4.8//0.1.4.9//0.1.5//0.1.7//0.1.7.1//0.1.7.2//0.1.7.3//0.1.7.4//0.1.7.5//0.1.7.6//0.1.7.7//0.1.8//0.1.9//0.1.9.1//0.1.9.11//0.1.9.12//0.1.9.13//0.1.9.2//0.1.9.3//0.1.9.8//0.1.9.9//0.1.9.9.1//1.0.0.1//1.0.0.2//1.0.0.3//1.0.0.3.1//1.0.0.4//1.0.0.5//0.0.0.1-SNAPSHOT//0.0.11-SNAPSHOT//0.0.1576066498-SNAPSHOT//0.0.1576066912-SNAPSHOT//0.0.1576209616-SNAPSHOT//0.0.1576677646-SNAPSHOT//0.0.1576722159-SNAPSHOT//0.0.1576732580-SNAPSHOT//0.0.1576737990-SNAPSHOT//0.0.1576757185-SNAPSHOT//0.0.1576812388-SNAPSHOT//0.0.1576817712-SNAPSHOT//0.0.1576821661-SNAPSHOT//0.0.1576821977-SNAPSHOT//0.0.1576825998-SNAPSHOT//0.0.1577182101-SNAPSHOT//0.0.1577266235-SNAPSHOT//0.0.1577267400-SNAPSHOT//0.0.1577268933-SNAPSHOT//0.0.2-SNAPSHOT//0.0.3-SNAPSHOT//0.0.4-SNAPSHOT//0.0.4.1-SNAPSHOT//0.0.4.2-SNAPSHOT//0.0.4.4-SNAPSHOT//0.0.4.5-SNAPSHOT//0.0.5-SNAPSHOT//0.0.5.11151113-SNAPSHOT//0.0.5.2-SNAPSHOT//0.0.5.2.1-SNAPSHOT//0.0.5.20180829-SNAPSHOT//0.0.5.20181115-SNAPSHOT//0.0.5.4-SNAPSHOT//0.0.5.4.181113-SNAPSHOT//0.0.5.5-SNAPSHOT//0.0.6-SNAPSHOT//0.0.7-SNAPSHOT//0.0.8-SNAPSHOT//0.0.9-SNAPSHOT//0.0.91576063257-SNAPSHOT//0.0.91576066026-SNAPSHOT//0.1.0-SNAPSHOT//0.1.1-SNAPSHOT//0.1.2-SNAPSHOT//0.1.2.2-SNAPSHOT//0.1.2.3-SNAPSHOT//0.1.2.4-SNAPSHOT//0.1.2.5-SNAPSHOT//0.1.2.6-SNAPSHOT//0.1.2.7-SNAPSHOT//0.1.3-SNAPSHOT//0.1.3.1-SNAPSHOT//0.1.3.3-SNAPSHOT//0.1.3.4-SNAPSHOT//0.1.4-SNAPSHOT//0.1.4.1-SNAPSHOT//0.1.4.4-SNAPSHOT//0.1.4.5-SNAPSHOT//0.1.4.6-SNAPSHOT//0.1.4.7-SNAPSHOT//0.1.4.9-SNAPSHOT//0.1.4.l-SNAPSHOT//0.1.4.y-SNAPSHOT//0.1.4.yl-SNAPSHOT//0.1.4.yy-SNAPSHOT//0.1.5-push-SNAPSHOT//0.1.5-SNAPSHOT//0.1.5.1-SNAPSHOT//0.1.5.2-SNAPSHOT//0.1.5.3-SNAPSHOT//0.1.5.4-SNAPSHOT//0.1.5.5-SNAPSHOT//0.1.5.6-SNAPSHOT//0.1.5.l-SNAPSHOT//0.1.5.testpush-SNAPSHOT//0.1.5.y-SNAPSHOT//0.1.5.yl-SNAPSHOT//0.1.6-SNAPSHOT//0.1.7-SNAPSHOT//0.1.7.1-SNAPSHOT//0.1.7.2-SNAPSHOT//0.1.7.3-SNAPSHOT//0.1.7.4-SNAPSHOT//0.1.7.6.1-SNAPSHOT//0.1.8-SNAPSHOT//0.1.9.15-SNAPSHOT//0.1.9.16-SNAPSHOT//0.1.9.2-SNAPSHOT//0.1.9.6-SNAPSHOT//0.1.9.7-SNAPSHOT//0.1.9.9.2-SNAPSHOT//0.1.9.9.3-SNAPSHOT//0.2.0-SNAPSHOT//1.0.0.0-SNAPSHOT//1.0.0.1-SNAPSHOT//1.0.0.2-SNAPSHOT//1.0.0.3-lv-SNAPSHOT//1.0.0.3-SNAPSHOT//1.0.0.4-SNAPSHOT//1.0.0.5-SNAPSHOT//1.0.0.6-SNAPSHOT//1.0.0.7-SNAPSHOT//1.0.0.8-SNAPSHOT//1.0.0.9-SNAPSHOT//1.0.1-SNAPSHOT//1.0.1.0-SNAPSHOT//1.0.1.1-SNAPSHOT//1.0.1.2-SNAPSHOT//1.0.1.3-SNAPSHOT"; // the above string
        String[] versions = data.split("//");
        List<ComparableVersion> comparableVersions = Arrays.stream(versions)
                .map(ComparableVersion::new)
                .distinct()
                .collect(Collectors.toList());
        Collections.sort(comparableVersions);
        System.out.println(comparableVersions);
    }
}

This assumes that ComparableVersion.equals() is not going to return true for any pair of versions which you don't think are equal.

In this case, the latter of 0.0.4 and 0.0.4. will be removed from the stream.

score 1 · Answer 2 · answered Jan 27 '23 at 20:39

It seems like Maven's ComparableVersion comparison algorithm doesn't respect the rule of transitivity, namely: if a < b and b < c then a < c. More info here.

Therefore Timsort, which assumes that a comparison algorithm respects transitivity, will not work in many cases.

Here's an example of a test in the Maven repo that will fail since transitivity is not followed:

    @Test
    public void transitivity() {
        ComparableVersion c1 = new ComparableVersion("c1");
        ComparableVersion alpha13 = new ComparableVersion("0.0.0-alpha13");
        ComparableVersion allZeroes = new ComparableVersion("0.0.0");

        // A: c1 < 0.0.0-alpha13
        System.out.println(c1.compareTo(alpha13));
        assertTrue(c1.compareTo(alpha13) < 0, "c1 < 0.0.0-alpha13");
        
        // B: 0.0.0-alpha13 < 0.0.0
        System.out.println(alpha13.compareTo(allZeroes));
        assertTrue(alpha13.compareTo(allZeroes) < 0, "0.0.0-alpha13 < 0.0.0");

        // Since c1 < 0.0.0-alpha13 (A) and 0.0.0-alpha13 < 0.0.0 (B), Therefore c1 < 0.0.0
        System.out.println(c1.compareTo(allZeroes));
        assertTrue(c1.compareTo(allZeroes) < 0, "c1 < 0.0.0");
    }

The output will be:

-1
-5
2

org.opentest4j.AssertionFailedError: c1 < 0.0.0 ==> 
Expected :true
Actual   :false

You could try running your program with the following flag: -Djava.util.Arrays.useLegacyMergeSort=true if you would like your program to not crash (more info here), but I believe that the same array may be sorted in different and conflicting ways since transitivity isn't respected.

I would raise an issue for this in the Maven repo. But, it doesn't seem like they allow issues.

maven-artifact ComparableVersion doesn't work well with java colllections sort algorithm timsort: Comparison method violates its general contract

2 Answers2