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~

Answer 1

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.

Answer 2

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.